問題文

IOI 町には $N$ 個の交差点があり，$1$ から $N$ までの番号が付いている．また，$M$ 本の道があり，$1$ から $M$ までの番号が付いている．それぞれの道は $2$ 個の異なる交差点を双方向に結んでいる．道 $i$ ($1 \leq i \leq M) は交差点$A_i$と交差点$B_i$ を結んでいる．$2$ 本の異なる道が同じ交差点の組を結ぶことはない．これらの道には $1$ 以上 $M$ 以下の整数で表される色が塗られており，道 $i$ の現在の色は $C_i$ である．複数の道が同じ色で塗られているかもしれない．

JOI 社は IOI 町の交差点を移動するロボットを開発した．あなたがこのロボットに道の色を指示すると， ロボットは指示された色の道を通り隣接した交差点に移動する．ただし，ロボットが現在いる交差点につな がれた道のうちに，指示された色の道が $2$ 本以上存在すると，次に進むべき道を判別できずに停止してし まう．

あなたの目的は，現在交差点 $1$ にいるロボットに何回かの指示を出して，交差点 $N$ に移動させることで ある．ただし，現在の道の色ではそれができるとは限らないため，何本かの道の色を事前に塗り替えること で，ロボットを交差点 $N$ に移動させることができるようにしたい．道 $i$ ($1 \leq i \leq M$) は $P_i$ 円をかけて，$1$ 以上 $M$ 以下の好きな整数の色に塗り替えることが出来る．

交差点と道の情報が与えられたとき，必要な金額の最小値を求めるプログラムを作成せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 N に移動させることができない場合は，代わりに -1 を出力せよ．

入力

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

$N\ M$
$A_1\ B_1\ C_1\ P_1$
$\vdots$
$A_M\ B_M\ C_M\ P_M$

出力

標準出力に必要な金額の最小値を $1$ 行で出力せよ．ただし，どのように道の色を塗り替えてもロボットを 交差点 $N$ に移動させることができない場合は，代わりに -1 を出力せよ．

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

3

5 2
1 4 1 2
3 5 1 4

-1

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

1

制約

• $2 \leq N \leq 10^5$．
• $1 \leq M \leq 2 \times 10^5$．
• $1 \leq A_i < B_i \leq N$ ($1 \leq i \leq M$)．
• $(A_i, B_i) \neq (A_j, b_j)$ ($1 \leq i < j \leq M$)．
• $1 \leq C_i \leq M$ ($1 \leq i \leq M$)．
• $1 \leq P_i \leq 10^9$ ($1 \leq i \leq M$)．

小課題

1. ($34$ 点) $N \leq 1000$, $M \leq 2000$．
2. ($24$ 点) $P_i = 1$ ($1 \leq i \leq M$)．
3. ($42$ 点) 追加の制約はない．