D - バスと避けられない運命 Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

高橋君は、バスがあまり好きではありません。ですが、社会に出ると、バスを乗るという行為を避けることはできません。

社会人になると、自宅から会社まで、バスで通わなければなりません。高橋君はまだ内定を貰っていないので、会社の場所は解りません。

高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。 この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。

追記：なお、最悪のケースとは、バスに乗る時間の合計が最も短くなるように、乗るバスを選択した時に、最もバスに乗る時間の合計が長くなってしまうような位置に会社があるケースのことを指します。また、自宅から会社に行く際に、高橋君が乗るバスを選ぶことができ、高橋君はバスに乗る時間の合計が最も短い経路を選択するものとします。

各バスは、2 つのバス停を往復するように走っており、行き・帰りでかかる時間に差はありません。 バスにはいつでも乗ることが可能であり、乗継にかかる時間などは無視することが可能です。

また、自宅や会社はバス停に隣接しており、他のバス停まで歩いたり、バス以外の手段で移動することはできません。

高橋君が引っ越すべき場所を求め、そこに引っ越した際の、バスに乗らなければならない時間の最大値を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1 t_1
a_2 b_2 t_2
：
a_M b_M t_M
  • 1 行目には、バス停の数を表す整数 N (2 ≦ N ≦ 300) と、路線の数を表す整数 M (N - 1 ≦ M ≦ 44850) が、スペース区切りで与えられる。
  • 続く 2 行目から M 行は、バスの情報を表す。 i 番目の行には、バスの出発地点と往復する 2 つのバス停を表す番号 a_i, b_i (1 ≦ a_i, b_i ≦ N) と、その移動に何分かかるかを表す数字 t_i (1 ≦ t_i ≦ 1000) が、それぞれ整数で与えられる。
  • 辿り着けないバス停のペアは存在しないことが保証されている。
  • a_i ≠ b_i であることが保障されている。
  • ある 2 つのバス停を往復する路線は、高々 1 つしか存在しない。

出力

高橋君が引っ越した後、最も長くバスに乗らないといけない時にかかってしまう時間を、 1 行で出力せよ。出力の末尾には改行をいれること。

入力例1

3 2
1 2 10
2 3 10

出力例1

10

バス停 1 からバス停 2 に行くのには、10 分かかります。 バス停 1 からバス停 3 に行くのには、20 分かかります。 バス停 2 からバス停 3 に行くのには、10 分かかります。 よって、バス停 2 に引っ越した時、乗車時間の最大値は 10 分となり、これが最も良い引っ越し先となります。

入力例2

5 5
1 2 12
2 3 14
3 4 7
4 5 9
5 1 18

出力例2

26

バス停 3 に引っ越すと最善となります。

入力例3

4 6
1 2 1
2 3 1
3 4 1
4 1 1
1 3 1
4 2 1

出力例3

1

複数の経路があっても、遠回りしないことに注意してください。