問題 B - shortest path

Time Limit: 2 seconds / Memory Limit: 256 MB

問題

うさぎの国は，非常に細長い形状をしている．番号 0 から番号 N - 1 までで表される N 個の都市があり，これらはだいたい一直線上に並んでいる．都市間を移動するためには，距離などによるあるコストがかかる．都市 x から都市 y へ直接移動するためのコストは，基本的には D |x - y| である．ここで |x - y| は x - y の絶対値である．しかし，諸般の事情によりいくつかの都市間の移動のコストは異なり，各 i (1 ≤ i ≤ M) に対し，都市 A_i から都市 B_i への直接の移動または都市 B_i から都市 A_i への直接の移動にかかるコストは C_i である．

都市 S に住んでいるうさぎは，都市 T において年末に開催されるある展示即売会で目当ての本や CD を手に入れるため，旅の準備をすることにした．都市 S から都市 T まで直接行くことも，他の都市をいくつか経由して行くことも可能である．今から準備しておけば，時間の心配はないだろう．というわけで，コストの合計を最小化したい．

入力

N M D S T
A1 B1 C1
...
AM BM CM

1 行目は 5 つの整数 N, M, D, S, T を含む．

続く M 行のうち i 行目 (1 ≤ i ≤ M) は，3 つの整数 A_i, B_i, C_i を含む．

出力

都市 S から都市 T へ行くためのコストの合計の最小値を 1 行に出力せよ．

制約

• 2 ≤ N ≤ 100,000．
• 1 ≤ M ≤ 100,000．
• 1 ≤ D ≤ 10,000．
• 0 ≤ S < T ≤ N - 1．
• 0 ≤ A_i < B_i ≤ N - 1．
• i ≠ j に対し，(A_i, B_i) ≠ (A_j, B_j)．
• 1 ≤ C_i < D(B_i - A_i)．

部分点

100 点中 25 点分のデータは以下を満たす．

• 2 ≤ N ≤ 100．

入出力例

入力例 1

5 2 4 0 4
0 2 2
1 3 3

出力例 1

10

例えば，都市 2 を経由するとよい．都市 2 から都市 4 への移動にかかるコストは 4 × |2 - 4| = 8 である．

入力例 2

10 3 5 1 8
0 9 1
1 3 3
4 8 4

出力例 2

11

都市 0 と都市 9 を経由するとよい．

入力例 3

6 6 6 1 3
4 5 1
3 5 1
2 4 1
0 5 19
0 2 1
0 1 1

出力例 3

5

都市 0, 2, 5, 4 を経由するとよい．