Farmer John 发现了制作威斯康星州最甜黄油的秘诀：糖。他知道在牧场放一块方糖，$N$ 头牛（$1\le N\le500$）就会舔它，产出能卖得更贵的超甜黄油。当然，额外收入用来给牛买奢侈品。

FJ 是个狡猾的农夫。像当年的 Pavlov 一样，他知道能训练牛听到铃声就去某牧场。他准备在那里放糖，下午中间时分摇铃，使晚间挤奶产出完美牛奶。

他知道每头牛待在给定牧场（不一定独处）。给定牛所在牧场和牧场间道路，找到放方糖的牧场，使摇铃时牛所走总距离最小。FJ 知道牧场的连通情况足以保证总有解。

输入格式

• 第 $1$ 行：空格分隔的整数：牛数 $N$，牧场数 $P$（$2\le P\le800$），道路数 $C$（$1\le C\le1{,}450$）。牛唯一编号 $1\ldots N$，牧场唯一编号 $1\ldots P$。

• 第 $2\ldots N+1$ 行：每行一个整数，表示一头牛吃草的牧场；牛 $i$ 的牧场在第 $i+1$ 行。

• 第 $N+2\ldots N+C+1$ 行：每行三个空格分隔的整数，表示两牧场间一条道路及长度。道路可双向通行，任意牧场对之间直接道路至多一条。前两整数在 $1\ldots P$，第三在 $1\ldots225$。

输出格式

• 第 $1$ 行：一个整数，牛前往放方糖的牧场所走总距离的最小值。

样例

输入格式 1

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

输出格式 1

8

说明

下图用几何方式表示连接：

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

在牧场 $4$ 放糖，牛 $1$ 走 $3$ 单位，牛 $2$ 走 $5$，牛 $3$ 走 $0$，总计 $8$。

题目作者：Greg Galperin，2001 年