P1294 Gaoshou Goes for a Walk

Gaoshou (高手) has recently fallen in love, but it is unrequited. “Even unrequited love is still a complete love.” Gaoshou has never given up pursuing it. Today, on this sunny morning, the sun slowly rose from the west. So she found Gaoshou and hoped to take a walk with him on Aotou Mountain before morning reading begins. Of course, Gaoshou would not miss this long‑awaited opportunity; he has prepared everything.

There are $n$ viewpoints on Aotou Mountain, and there are $m$ footpaths between pairs of viewpoints. Gaoshou’s crush does not like anything too thrilling, so Gaoshou will not choose viewpoints that have no roads at all. In addition, she does not like to visit the same viewpoint more than once. Gaoshou wants their walking distance together to be as long as possible (while viewing the scenery, she will ignore Gaoshou). It is known that Gaoshou’s shuttle can start at any viewpoint and end at any viewpoint.

The first line contains two space‑separated integers $n$ 、 $m.$ After that, there are $m$ lines, each describing one footpath: the indices of its two endpoints and its length.

Output a single integer, representing the maximum distance they can stay together.

Constraints: For $100\%$ of the testdata: $n \le 20$, $m \le 50$. It is guaranteed that there is no more than one footpath between any pair of viewpoints. Translated by ChatGPT 5