問題
A 君は高校の休みを利用して、高速バス(以下、「バス」 )で一人旅をする計画を立てています。まず、A 君は一番行ってみたい町を選んでそこを目的地にしました。次に出発地から目的地までバスを乗り継いでいくルートを決めなければなりません。乗り継ぎをするときは、バスを降りてから別のバスに乗り換えるので、それぞれのバスの乗車券が必要になります。
A 君は親戚のおじさんからバスの割引券を何枚かもらいました。 この券を 1 枚使うと乗車券 1 枚を半額で購入できます。例えば、図 1 の出発地5から目的地1へ行く場合には、5→4→6→2→1と5→3→1の二つの経路が考えられます。割引券が 2 枚あるとすると、交通費を最も安くするには5→4→6→2→1の経路をたどった場合、4→6と6→2の路線に割引を利用し、合計料金は 4600円となります。一方、5→3→1の経路をたどった場合、5→3と3→1の路線に割引を利用し、合計料金は 3750 円となります。
A 君は観光にお金を回したいので、交通費はできるだけ少なくしようと考えています。そこで A 君は、出発地から目的地までの最も安い交通費を求めるプログラムを作成することにしました。
割引券の枚数、バスがつなぐ町の数、バスの路線数、各バスの路線情報を入力とし、出発地から目的地までの最も安い交通費を出力するプログラムを作成してください。各バスは双方向に同一料金で運行しています。また、町の数を n とすると、町にはそれぞれ異なる 1 から n までの番号が振られています。出発地から目的地までの経路は必ず存在するものとします。
入力
c n m s d a1 b1 f1 a2 b2 f2 : am bm fm
1 行目に割引券の枚数 c (1 ≤ c ≤ 10)、バスがつなぐ町の数 n (2 ≤ n ≤ 100)、バスの路線数 m (1 ≤ m ≤ 500)、出発地の町番号 s と目的地の町番号 d (s≠d) が与えられます。
続く m 行に第 i のバスの路線情報 ai,bi,fi (1 ≤ ai,bi ≤ n, 1000 ≤ fi ≤ 10000) が与えられます。ai,bi はバスの路線の始点と終点の町番号、fi はこの路線の料金を表す100 刻みの整数です。
出力
最も安い交通費を１行に出力します。
入出力例
入力例1
1 3 3 1 3 1 3 2000 1 2 1000 2 3 1000
出力例1
1000
入力例2
2 3 3 1 3 1 3 2300 1 2 1000 2 3 1200
出力例2
1100