ハイキング Bash(Beta)編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

paiza 君は、夏休みにある高原へハイキングをしに出かける予定です。paiza 君は、高原へ到着したら、その高原の各地点間の最短移動時間のうち最も時間のかかる経路をまずハイキングして、その後昼食をとるという計画を立てました。paiza 君が高原へ到着してから昼食を取るまでにハイキングした経路とその移動時間を出力してください。各地点間の最短移動時間のうち最も時間のかかる経路が複数存在する場合は、そのうちのどれかひとつを出力してください。また、ある地点間に経路が存在しない場合は、paiza 君は移動できないことに注意してください。

入力される値

N M
a_1 b_1 c_1
...
a_M b_M c_M

1 行目に、地点の個数を表す整数 N と、各地点を結ぶハイキングコースの本数を表す整数 M が与えられます。

i + 1 行目にハイキングコース i を表す整数の組 (a_i, b_i, c_i) が与えられます。ハイキングコース i は、地点 a_i から地点 b_i へのコースで、その移動時間は c_i です。(1 ≦ i ≦ M)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 合計 2 行出力してください。1 行目には paiza 君がハイキングした移動時間を出力し、2 行目には paiza 君が移動する経路でたどる地点を順番に左から半角スペース区切りで出力してください。

また末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

入力はすべて整数

2 ≦ N ≦ 100

1 ≦ M ≦ N × (N - 1)

1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)

a_i ≠ b_i (1 ≦ i ≦ M)

1 ≦ c_i ≦ 10 (1 ≦ i ≦ M)

同じ地点の組（順序組）は 2 回以上入力されない

入力例1: 3 6
1 2 10
2 1 1
1 3 2
3 1 3
2 3 4
3 2 1

出力例1: 3
1 3 2

入力例2: 5 7
1 2 4
1 3 9
2 4 1
4 5 3
5 2 3
3 4 2
1 4 6

出力例2: 9
1 3

入力例3: 5 4
1 3 1
3 5 1
5 4 1
4 2 1

出力例3: 4
1 3 5 4 2

問題一覧へ戻る