레이팅 미적용JOI 王国は N 個の都市からなる王国であり,これらの都市には 1 から N までの番号が付けられている.
JOI 王国には,これらの都市を結ぶ 一方通行 の高速道路が M 本あり, 1 から M までの番号が付けられている.
高速道路 i ( \(1 \le i \le M\) ) を通ると都市 A i から都市 B i に移動することができ,通行にかかる時間は L i である.
それぞれの高速道路を通るたびに,通行料金が発生する.
高速道路 i の通行料金は最も安い時で C i だが,JOI 王国の労働者は皆時間外労働を嫌うため,ある基準となる時刻 0 から離れれば離れるほど通行料金が増えてしまう.
具体的には,都市 A i を時刻 t に出発して高速道路 i を通行した場合,通行料金は定数 K を用いて C i + K × |t| と表される.
ただし, |t| は t の絶対値を表す.
都市 1 に住んでいるあなたは,友達の住む都市 N へ出かける計画を立てている.
あなたは高速道路を通って都市 1 から都市 N まで移動したいので,まずはそれが可能かどうか確かめ,可能ならば通行料金の総和が最小でいくらになるかも求めたい.
ただし,移動経路や各都市を出発するタイミングは自由に決めることができる.
特に,都市 1 を負の時刻に出発したり,高速道路を通行せずどこかの都市に留まっている時間があったりしてもよい.
高速道路の情報および定数 K が与えられたとき,高速道路を通って都市 1 から都市 N まで移動することが可能かどうか判定し,
可能な場合は通行料金の総和の最小値を求めるプログラムを作成せよ.
なお,この問題の制約の下では,高速道路を通って都市 1 から都市 N まで移動することが可能な場合,通行料金の総和の最小値は必ず整数になることが証明できる.
2 ≦ N ≦ 4 000 .
1 ≦ M ≦ 8 000 .
0 ≦ K ≦ 100 000 .
1 ≦ A i ≦ N ( \(1 \le i \le M\) ).
1 ≦ B i ≦ N ( \(1 \le i \le M\) ).
A i ≠ B i ( \(1 \le i \le M\) ).
1 ≦ L i ≦ 1 000 000 ( \(1 \le i \le M\) ).
0 ≦ C i ≦ 10 9 ( \(1 \le i \le M\) ).
入力される値はすべて整数である.
( 9 点) \(N \le 100\) , \(M \le 200\) , K = 0 .
( 21 点) \(N \le 100\) , \(M \le 200\) , L i ≦ 20 ( \(1 \le i \le M\) ).
( 13 点) \(N \le 100\) , M = N - 1 , A i = i , B i = i+1 ( \(1 \le i \le M\) ).
( 23 点) \(N \le 100\) , \(M \le 200\) であり,以下の制約を満たす.
N は偶数, [ B i ÷ 2 ] - [ A i ÷ 2 ] = 1 ( \(1 \le i \le M\) ).
ここで, [ x ] は x 以下の最大の整数を表す.
( 16 点) \(N \le 100\) , \(M \le 200\) .
( 11 点) N ≦ 1 500 , M ≦ 3 000 .
( 7 点) 追加の制約はない.
入力は以下の形式で与えられる.
N M K
A 1 B 1 L 1 C 1
A 2 B 2 L 2 C 2
...
A M B M L M C M
高速道路を通って都市 1 から都市 N まで移動することが不可能な場合は, -1 を出力せよ.
可能な場合は,通行料金の総和の最小値を表す整数を 1 行で出力せよ.
4 4 2
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3
15
4 4 0
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3
9
2 1 10
2 1 4 7
-1
4 3 5
1 2 3 1
2 3 1 10
3 4 7 6
37
8 8 2
1 2 1 5
5 6 3 1
2 4 10 18
3 5 3 1
1 3 4 2
5 6 2 2
2 5 2 3
6 8 1 1
25
6 10 100000
4 2 212037 752027141
2 5 667097 1571491
2 1 769275 576006950
1 2 711969 526189398
5 3 733555 206320177
3 4 364807 802102091
1 4 467240 183184247
3 5 44994 15991843
5 3 613192 782356546
4 6 832593 639529758
47546714005