Hot Spring Trip

Time Limit : 1 sec, Memory Limit : 65536 KB

温泉旅行

温泉好きのたけしさんは、次の長期休暇を利用してとある温泉地への旅行を計画しています。移動は長距離バスを乗り継ぎ、なるべくお金をかけずに目的地へたどり着きたいと思っています。貯金があるとはいえ、資金に心許ないたけしさんは、おじいさんに相談することにしました。計画を聞いて感心したおじいさんは、たけしさんに特別な切符を渡しました。

その切符は、長距離バスの連続した2区間を1回だけ無料で乗れるというものでした。使いようによってはかなりの移動費削減が見込めますが、より大きな効果を発揮させるためにはしっかりした計画を練る必要があります。

出発地と目的地、及び中継地点が合わせてn個、2つの地点を結ぶ路線がm個与えられます。各地点にはそれぞれ1からnまでの数字が割り振られています。出発地は1、目的地はnです。路線の情報は、その路線が結ぶ2つの地点aとb、及びその料金cで表されます。特別な切符の効力により、任意の地点から、一度だけ連続した2つの路線を料金0で通過することができます。ただし、途中で目的地を通過しても、目的地にたどり着いたことにはなりません。

出発地、目的地、及び中継地点の総数nと路線の数m、各路線の情報を入力とし、料金の最小値を出力するプログラムを作成してください。ただし、必ず出発地から目的地へと到達する経路が存在するものとします。またnは2以上100以下、cは1以上1000以下とします。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の通りです。

1行目 n m (整数 整数;半角空白区切り)
2行目 第1の路線の情報 a1 b1 c1 (整数 整数 整数;半角空白区切り)

m+1行目 第mの路線の情報 am bm cm

出力

入力データセットごとに、料金の最小値を出力します。

入力例

2 1
1 2 5
3 2
1 2 5
2 3 5
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 5 9
4 6 8
0 0

出力例

5
0
7

Source: PC Koshien 2011, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2011
(revised version)
http://www.pref.fukushima.jp/pc-concours/