12/04/15 16:45:36.91 hPdx0Eik0
佐藤家の長男VIP君は今年で6歳になる。そこでVIP君の両親は彼にはじめてのおつかいをさせることにした。
VIP君は両親から晩飯に必要な食材を購入するためのお店の位置と距離の書いた地図が与えられる。
VIP君はまだ６歳なので最小の距離でお使いにいき、はやく帰ってきてもらいたい。
VIP君はまだ幼いので決められた方向にしか進むことができない。
両親は計算が苦手だったのでプログラマーである>>1に代わりにVIP君が歩く最小の距離を計算してもらいたい。
>>1の仕事は自宅と各お店の距離が与えられるのでその距離の総和の最小値を求めることである。
ただしお店の数は２以上15以下で距離は０以上５００以下であることが約束されている。
入力は以下の様になる
1行目: 自宅+お店の数 道の数
2行目～道の数分だけ: 出発点 終点 距離
例:
5 8
0 1 3
1 2 5
2 3 5
3 4 3
4 0 7
4 1 6
0 3 4
2 0 4
出力: 22