AT_wupc2012_5 会場への道

[problemUrl]: https://atcoder.jp/contests/wupc2012/tasks/wupc2012_5 いよいよコンテスト前日になった．当日に備えて会場への経路を確認しておこう！会場まで徒歩で移動するつもりだ．僕が住む街から会場がある街（早稲田）まで，いくつかの街を経由して行く．街同士は道でつながっており，街から街へは道を経由しないと移動できない． コンテストで絶対に勝ちたい．だから満を持すために験を担ごう．僕は4か7で割り切れる数は縁起の良い数だと信じている．出発時間を0としたときに，会場へ到達した時間が4か7で割り切れると良い気分になれそうだ．だけど，4でも7でも割り切れない時間に到達した時は，コンテストで負けてしまう気がする．コンテストで勝つためには，多少遠回りでも4か7で割り切れる時間に到着するように移動したい． 会場までの移動方法は自由だ．一度通った道を引き返しても，既に通った街や僕が住む街に戻っても良い．ただし，道の途中で引き返したり，一度会場に着いてから引き返すようなことはできない． さぁ，この条件を満たすように移動した時，会場に到着するまでにかかる最短時間を求めてみよう！ $ N $個の街を繋ぐ$ M $個の道路の情報が与えられる．各道路は異なる2つの街を繋いでおり，指定された時間をかけて双方向に移動することができる．道路の情報は2つの異なる街の番号($ 0 $～$ N-1 $)と時間で与えられる．「僕」のいる街の番号を$ 0 $，会場のある街の番号を$ N-1 $，そして出発の時間を$ 0 $とする．会場のある街への到達時間が$ 4 $か$ 7 $で割り切れるような方法で移動した時，その最短の到達時間を出力するプログラムを作成せよ．ただし，一度会場に着いたらそれ以上移動することはできない．また，道の途中で引き返したり，街や道の途中で休憩を取ることはできない． 入力は以下の形式で標準入力から与えられる． > $ 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 単位時間以内に移動できることが保証される．

N/A

N/A