E - 会場への道 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

　いよいよコンテスト前日になった．当日に備えて会場への経路を確認しておこう！会場まで徒歩で移動するつもりだ．僕が住む街から会場がある街（早稲田）まで，いくつかの街を経由して行く．街同士は道でつながっており，街から街へは道を経由しないと移動できない．

　コンテストで絶対に勝ちたい．だから満を持すために験を担ごう．僕は4か7で割り切れる数は縁起の良い数だと信じている．出発時間を0としたときに，会場へ到達した時間が4か7で割り切れると良い気分になれそうだ．だけど，4でも7でも割り切れない時間に到達した時は，コンテストで負けてしまう気がする．コンテストで勝つためには，多少遠回りでも4か7で割り切れる時間に到着するように移動したい．

　会場までの移動方法は自由だ．一度通った道を引き返しても，既に通った街や僕が住む街に戻っても良い．ただし，道の途中で引き返したり，一度会場に着いてから引き返すようなことはできない．

　さぁ，この条件を満たすように移動した時，会場に到着するまでにかかる最短時間を求めてみよう！

問題文

　N個の街を繋ぐM個の道路の情報が与えられる．各道路は異なる2つの街を繋いでおり，指定された時間をかけて双方向に移動することができる．道路の情報は2つの異なる街の番号(0～N-1)と時間で与えられる．「僕」のいる街の番号を0，会場のある街の番号をN-1，そして出発の時間を0とする．会場のある街への到達時間が4か7で割り切れるような方法で移動した時，その最短の到達時間を出力するプログラムを作成せよ．ただし，一度会場に着いたらそれ以上移動することはできない．また，道の途中で引き返したり，街や道の途中で休憩を取ることはできない．
図1：入力例 3の街と道の様子

入力

入力は以下の形式で標準入力から与えられる． 
N　M
f_{1}　t_{1}　c_{1}
...
f_{m}　t_{m}　c_{m}
  • 1 行目に街の数を表す N(2 ≦ N ≦ 1000) と道路の数 M(1 ≦ M ≦ min(10000, N*(N-1)/2)) が半角スペース区切りで与えられる．
  • 2 行目～ M+1 行目にはそれぞれ道路の情報，つまり，道路が結ぶ二つの街の番号 f_{i} と t_{i}，および移動にかかる時間 c_{i} が半角スペース区切りで与えられる．
  • 各 i について 0 ≦ f_{i} ≦ N-1 かつ 0 ≦ t_{i} ≦ N-1 ，  f_{i} ≠ t_{i} ， 1 ≦ c_{i} ≦ 100000 を満たす．
  • 二つの街を結ぶ道路の数は高々 1 つである．街から一本も道路が出ていないこともある．

出力

会場まで条件を満たすように移動するとき，その最小時間を標準出力に 1 行で出力せよ．
なお，会場までは必ず条件を満たすように移動できることが保証されている．

部分点

100点満点中，30点分については，上記条件に加え，会場まで 500 単位時間以内に移動できることが保証される．

入力例 1

2 1
0 1 4

出力例 1

4
  • スタートの街0からゴールの街1へ時間4をかけて移動できる．合計時間4は4の倍数であるので条件を満たす．したがって，答えは4である．

入力例 2

3 2
0 1 15
1 2 5

出力例 2

20
  • スタートの街0から街1へ時間15，街1からゴールの街2へ時間5をかけて移動できる．合計時間20は4の倍数であるので条件を満たす．したがって，答えは20である．

入力例 3

4 3
0 1 1
1 2 1
2 3 1

出力例 3

7
  • スタートの街0から街1へ時間1，街1から街2へ時間1，街2からゴールの街3へ時間1をかけて移動できる．スタートからゴールへ最短経路をたどって行くと合計時間3がかかるが，4でも7の倍数でもない．街1と街2の間を2往復すると合計時間7となり，7の倍数であるので条件を満たす．したがって，答えは7である．

Source Name

WUPC 2012