温泉好きのたけしさんは、次の長期休暇を利用してとある温泉地への旅行を計画しています。移動は長距離バスを乗り継ぎ、なるべくお金をかけずに目的地へたどり着きたいと思っています。貯金があるとはいえ、資金に心許ないたけしさんは、おじいさんに相談することにしました。計画を聞いて感心したおじいさんは、たけしさんに特別な切符を渡しました。
その切符は、長距離バスの連続した2区間を1回だけ無料で乗れるというものでした。使いようによってはかなりの移動費削減が見込めますが、より大きな効果を発揮させるためにはしっかりした計画を練る必要があります。
出発地と目的地、及び中継地点が合わせて n 個、2つの地点を結ぶ路線が m 個与えられます。各地点にはそれぞれ 1 から n までの数字が割り振られています。出発地は 1、目的地は n です。路線の情報は、その路線が結ぶ2つの地点 a と b、及びその料金 c で表されます。特別な切符の効力により、任意の地点から、一度だけ連続した2つの路線を料金0で通過することができます。ただし、途中で目的地を通過しても、目的地にたどり着いたことにはなりません。
出発地、目的地、及び中継地点の総数 n と路線の数 m、各路線の情報を入力とし、料金の最小値を出力するプログラムを作成してください。ただし、必ず出発地から目的地へと到達する経路が存在するものとします。
複数のデータセットが与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。
n m a1 b1 c1 a2 b2 c2 : am bm cm
1行目に出発地、目的地、及び中継地点の総数 n (2 ≤ n ≤ 100)と路線の数 m (1 ≤ m ≤ 300)が与えられます。続く m 行に各路線の情報 ai, bi, ci (1 ≤ ci ≤ 1000) が与えられます。
データセットの数は 40 を超えません。
入力データセットごとに、料金の最小値を1行に出力します。
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