配点 : 300点

問題文

くしらっちょさんが住む国には $N$ 箇所の町があり、それぞれの町には $1$ から $N$ の番号が割り振られています。また、町同士をつなぐ一方通行の道が $M$ 本あります。$i$ 番目の道は町 $a_i$ から町 $b_i$ へ移動することが可能で、その移動には $c_i$ 分かかります。

くしらっちょさんは魔法使いなので、次の2つの魔法を全体でそれぞれ $1$ 回まで、ある町の上にいるときに使うことができます。(魔法を使わなくてもよいです。また、どちらか一方のみ使ってもよいです。)

• 魔法1: 唱えるのに $X$ 分かかる。$M$ 本ある道をすべて、かかる時間はそのままで逆向きにする。つまり、$i$ 番目の道は町 $b_i$ から町 $a_i$ へ、$c_i$ 分で移動できるようになり、町 $a_i$ から町 $b_i$ へは行けなくなる。

• 魔法2: 唱えるのに $Y$ 分かかる。$i$ 番目の道について、その移動にかかる時間を以下のように更新する。

  • $c_i$ が偶数のとき: $c_i$ を $c_i \div 2$ に更新する。
  • $c_i$ が奇数のとき: $c_i$ を $c_i \times 2$ に更新する。

くしらっちょさんはいま頂点 $1$ にいます。頂点 $N$ まで最短で移動したとき、何分で移動できますか？ 頂点 $N$まで移動できない場合は -1 を出力してください。

制約

• $2 \leq N \leq 5 \times 10^4$
• $0 \leq M \leq 5 \times 10^4$
• $1 \leq a_i, b_i \leq N$（$1 \leq i \leq M$）
• $0 \leq c_i \leq 10^5$（$1 \leq i \leq M$）
• $0 \leq X, Y \leq 10^5$
• $a_i \neq b_i$
• $i \neq j \Rightarrow \{a_i, b_i\} \neq \{a_j, b_j\}$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

出力

$1$ 行で、頂点 $1$ から頂点 $N$ までにかかる最短時間を出力してください。頂点$N$に到達できない場合、-1を出力してください。

入力例1

3 2 10 100
1 2 5
3 2 10

25

• 頂点 $1$ から頂点$2$に移動する。$5$ 分かかる。
• 頂点 $2$ で魔法$1$を唱える。$10$ 分かかる。
• 頂点 $2$ から頂点$3$に移動する。$10$ 分かかる。

とすると、最短で頂点 $1$ から頂点 $3$ に移動できて、合計 $25$ 分かかります。

入力例2

3 2 10 1
1 2 5
3 2 10

21

• 頂点 $1$ から頂点 $2$ に移動する。$5$ 分かかる。
• 頂点 $2$ で魔法 $1$ を唱える。$10$ 分かかる。
• 頂点 $2$ で魔法 $2$ を唱える。$1$ 分かかる。
• 頂点 $2$ から頂点 $3$ に移動する。$5$ 分かかる。

とするのが最短で、合計 $21$ 分かかります。同じ頂点で魔法1と魔法2を唱えてもよいです。

入力例3

5 5 1 1
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1

-1

どのようにしても頂点 $1$ から頂点 $5$ に移動できません。-1を出力してください。

入力例4

7 10 6 13
1 4 10
1 5 3
1 6 4
4 2 10
4 3 5
4 6 6
5 4 2
5 6 5
6 1 9
7 5 9

18