問題文

$N$ 個の町と、$M$ 本の橋があります。$i$ 本目の橋は、町 $u_i$ と町 $v_i$ を結ぶ橋で、どちらにも渡ることができ、渡るのに $C_i$ 円かかります。

あなたは、$K$ 枚のクーポンを持っており、橋を渡るときにクーポンを1枚使うと、橋を渡る料金を $0$ 円にすることができます。

あなたは、現在町 $1$ におり、町 $N$ に行きたいです。クーポンを適切に使用したときに、あなたが支払うべき料金の最小値を求めてください。

制約

• $2 \leq N,M \leq 10^5$
• $0 \leq K \leq 3$
• $1 \leq u_i<v_i \leq N$
• $1 \leq C_i \leq 10^9$
• $i \neq j \Rightarrow (u_i,v_i) \neq (u_j,v_j)$

入力

入力は以下の形式で標準入力から与えられる。

$N\ M\ K$
$C_1\ C_2\ldots\ C_M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

出力

一行に、町$N$へ行くために必要な料金の最小値を出力せよ。ただし、町$N$に到達できない場合は$-1$を出力せよ。最後に改行せよ。

サンプル

3 2 1
4 2 
1 2
2 3

2

5 4 2
4 2 3 9 
1 2
2 3
1 3
4 5

-1

7 10 1
565731850 55598766 527171038 341219331 325504904 409516626 583498624 3987342 112468674 114000403
1 4
1 5
1 6
2 3
2 4
3 4
3 5
5 7
5 6
6 7

3987342