問題


祝日のない六月に ahri は有給休暇を使って「うしたぷにきあ王国」へ旅行したいと考えています。 「うしたぷにきあ王国」には の都市と本の道があります。 番目の道の情報について以下の「」形式で入力から与えられます。

  • のとき電車で都市から都市へ双方向に移動できる、移動毎にお金を10000消費する
  • のとき都市から都市へ双方向に歩いて移動できる、移動毎に体力を10000消費する

ahri は体力の消費を最小限にしつつ 都市個のうち個を まで順番に旅行したいと考えています。 旅行するために ahri が用意しなければならない最低金額を答えてください。

制約


  • 都市と道は単純グラフ
  • 入力は整数

入力


出力


まで順番に旅行できる体力消費最小経路の中で最も低い金額を出力してください。

なお、個の中に到達できない都市が存在する場合は を出力してください。

サンプル


入力1
5 6
1 1 2
2 1 3
1 2 3
2 2 4
1 3 4
2 4 5
3
1 4 5
出力1
30000

ahri の目的は都市1から出発して都市4、都市5と旅行することです。

都市4から都市5へ移動するには歩くしかありませんが、都市1から都市4への移動は電車を使うことが出来ます。

したがって、都市1から出発して都市2、都市3、都市4と電車で移動し、都市4から都市5まで歩いて旅行するのが最善です。

お金は30000用意すれば良いです。

入力2
9 10
2 1 2
1 1 3
1 3 4
1 4 5
1 5 2
1 1 6
1 6 7
1 7 8
1 8 9
1 9 2
2
1 2
出力2
40000

都市2は都市1の隣にありますが ahri は歩きたくありません。

したがって、都市1から出発して都市3、都市4、都市5、都市2と移動して旅行するのが最善です。

他にも都市2へ到達する経路はありますが、40000以下にする方法はありません。

入力3
6 6
1 1 2
2 1 3
1 2 3
2 4 5
1 5 6
2 6 4
3
1 3 5
出力3
-1

目的地の都市に移動できないので を出力します。

入力4
10 20
2 1 6
2 8 3
1 6 3
2 4 2
2 6 9
2 6 4
2 10 3
1 7 3
2 4 5
1 8 4
1 7 4
1 5 9
1 2 1
1 5 10
1 2 5
1 3 5
1 9 8
2 1 5
2 6 8
1 1 3
5
3 4 6 7 8
出力4
90000

提出


Go (1.14)