L - Journey of a Wizard

配点 : 300点

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

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

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

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

  • が偶数のとき: を に更新する。
  • が奇数のとき: を に更新する。

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

• （）
• （）
• 入力はすべて整数

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

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

3 2 10 100
1 2 5
3 2 10

25

• 頂点 から頂点に移動する。 分かかる。
• 頂点 で魔法を唱える。 分かかる。
• 頂点 から頂点に移動する。 分かかる。

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

3 2 10 1
1 2 5
3 2 10

21

• 頂点 から頂点 に移動する。 分かかる。
• 頂点 で魔法 を唱える。 分かかる。
• 頂点 で魔法 を唱える。 分かかる。
• 頂点 から頂点 に移動する。 分かかる。

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

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

-1

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

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