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

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

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

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

制約

• 2 \leqq N \leqq 100\,000．
• 1 \leqq M \leqq 200\,000．
• 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)．
• (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M)．
• 1 \leqq C_i \leqq M (1 \leqq i \leqq M)．
• 1 \leqq P_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq M)．

小課題

1. (34 点) N \leqq 1\,000，M \leqq 2\,000．
2. (24 点) P_i = 1 (1 \leqq i \leqq M)．
3. (42 点) 追加の制約はない．

入力例 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

出力例 1

3

1 円で道 4 を色 3 から色 4 に塗り替え，2 円で道 6 を色 4 から色 2 に塗り替える．合計 3 円かかる．

この結果，交差点 1 にいるロボットに色 2 を指示することで，ロボットを交差点 2 に移動させることができる．続けて，ロボットに色 4 を指示することで，ロボットを交差点 4 に移動させることができる．

2 円以下でロボットを交差点 4 に移動させることは不可能であるため，3 を出力する．

入力例 2

5 2
1 4 1 2
3 5 1 4

出力例 2

-1

道をどのように塗り替えても，ロボットを交差点 5 に移動させることはできない．したがって，-1 を出力する．

入力例 3

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

出力例 3

1

この入力例は小課題 2 の制約を満たす．

入力例 4

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

出力例 4

7