AT_abc012_4 [ABC012D] バスと避けられない運命

[problemUrl]: https://atcoder.jp/contests/abc012/tasks/abc012_4 高橋君は、バスがあまり好きではありません。ですが、社会に出ると、バスを乗るという行為を避けることはできません。 社会人になると、自宅から会社まで、バスで通わなければなりません。高橋君はまだ内定を貰っていないので、会社の場所は解りません。 高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。 この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。 追記：なお、最悪のケースとは、バスに乗る時間の合計が最も短くなるように、乗るバスを選択した時に、最もバスに乗る時間の合計が長くなってしまうような位置に会社があるケースのことを指します。また、自宅から会社に行く際に、高橋君が乗るバスを選ぶことができ、高橋君はバスに乗る時間の合計が最も短い経路を選択するものとします。 各バスは、$ 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 $ 行で出力せよ。出力の末尾には改行をいれること。

### Sample Explanation 1 バス停 $ 1 $ からバス停 $ 2 $ に行くのには、$ 10 $ 分かかります。 バス停 $ 1 $ からバス停 $ 3 $ に行くのには、$ 20 $ 分かかります。 バス停 $ 2 $ からバス停 $ 3 $ に行くのには、$ 10 $ 分かかります。 よって、バス停 $ 2 $ に引っ越した時、乗車時間の最大値は $ 10 $ 分となり、これが最も良い引っ越し先となります。 ### Sample Explanation 2 バス停 $ 3 $ に引っ越すと最善となります。 ### Sample Explanation 3 複数の経路があっても、遠回りしないことに注意してください。