1648 - テレポート移動網

問題

人類は研究の末、ついにテレポート装置を利用した移動網を構築できるようになった。テレポート装置が設置できるのは$1$から$N$までの番号が付いた地点だけで、全部で$M$台のテレポート装置が設置されている。$i$番目のテレポート装置は地点$a_i$に設置されており、移動先$b_i$と使用コスト$f_i$が設定されている。地点 $a_i$にいる利用者は使用コスト$f_i$を支払うと地点$b_i$に移動できる。

テレポート装置の利用者は事前に申請をすれば、装置を他の地点に移設できる。装置１台を１つ離れた番号の地点に移設するごとに申請が１回必要で、１回当たり申請コスト$C$がかかる。申請には以下のルールがある。

１回の申請では、装置1台を移設前の地点から番号が１つだけ離れた地点にだけ移設できる。たとえば、地点7にあるテレポート装置は地点6か8だけに移設できる。また、地点1にある装置は2だけに、地点$N$にある装置は$N−1$だけにそれぞれ移設できる。

装置が移設されても、その装置により利用者が移動できる地点や使用コストは移設前と変わらない。

同じ装置の移設は何度でも申請することができる。

同じ装置の移設を何度も申請することで、２つ以上番号が離れた地点へ移設させることができる。たとえば、地点5にある装置を地点8に移設したいときは、5から6、6から7、7から8への各移設のために３回の申請が必要で、そのために$3×C$の申請コストがかかる。

あなたは、テレポート装置を利用して地点$1$から地点$N$まで移動する計画を立てているが、使用コストと申請コストの総和をできるだけ少なくして出費を抑えたいと思っている。

テレポート装置の情報と1回あたりの申請コストが与えられたとき、利用者が地点$1$から地点$N$へテレポートだけで移動するのにかかる、使用コストと装置の移設に必要な申請コストの総和の最小値を求めるプログラムを作成せよ。

入力

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

$N$ $M$ $C$
$a_1$ $b_1$ $f_1$
$a_2$ $b_2$ $f_2$
:
$a_M$ $b_M$ $f_M$

１行目に、地点の数$N$($2 \leq N \leq 200,000$)、テレポート装置の数$M$($1 \leq M \leq 100,000$)、１回あたりの申請コスト$C$($1 \leq C \leq 1,000$)が与えられる。続く$M$行に、$i$番目のテレポート装置が設置されている地点の番号$a_i$($1 \leq a_i \leq N$)、転送先の地点の番号$b_i$($1 \leq b_i \leq N$)、使用コスト$f_i$($1 \leq f_i \leq 1,000$)が与えられる。入力はすべて整数である。

出力

コストの総和の最小値を１行に出力する。ただし、どのようにしてもたどり着けない場合は、-1を出力する。

入出力例

入力例1

9 2 3
3 6 1
5 9 7

出力例1

17

入力例2

3 3 1
3 1 1
3 2 1
1 2 1

出力例2

-1

入力例3

10 4 1
1 9 1
5 10 1
9 5 3
10 5 1

出力例2

4

申請コスト１を使って地点１０にあるテレポート装置を地点９に移設することで、利用者は地点１から地点１０へ使用コスト３で移動することができるので、コストの総和の最小値は４になる。