Description

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.

Input Format

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 Format

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

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

150

Hint

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