Farmer John は Wisconsin で一番甘いバターを作る秘密、砂糖を発見しました。牧草地に角砂糖を置けば $N$ 頭（$1\le N\le500$）がなめ、とても甘いバターができ、高く売れます。増えたお金はもちろん牛のぜいたくに使います。

FJ は抜け目のない農夫です。昔の Pavlov のように、ベルを聞くと特定の牧草地に向かうよう訓練できると知っています。そこに砂糖を置き、午後の中頃に鳴らして、夜の搾乳で完璧な乳を得ます。

各牛は指定の牧草地にいます（独りとは限りません）。位置と牧草地間の道から、ベルで牛が歩く総距離を最小にする砂糖の牧草地を求めます。牧草地の接続は十分で必ず解があります。

入力

• 第 $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$ 行：空白区切りの整数 3 個は牧草地間の道と長さです。双方向に通れ、同じ 2 地を直接結ぶ道は最大 1 本。最初の 2 整数は $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 年