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 年