Minions Having Fun

Time limit2sMemory limit256 MB

Summary

Find a simple cycle in an undirected weighted graph maximizing the minimum edge weight plus the maximum edge weight on that cycle.

Level: Hard8 of 10
Topics: Graph, Union-find, Sorting, Greedy
Solved: No attempts yet

Problem

Gru went to the store, and now the minions are very bored with nothing to do. They decided to entertain themselves and came up with a competition, and absolutely all of them agreed to take part.

The competition works as follows. On the map of Gru's laboratory, n checkpoints are marked. Between them there are m two-way paths, and each path has several bananas lying on it. The minions are asked to start their route at any checkpoint, run along the paths, and then return to the starting checkpoint. A minion never runs along the same path more than once.

Suppose a minion runs some such cyclic route and passes along paths on which c1, c2, ..., ck bananas were lying, respectively. Then for this route it gets a number of points equal to min(c1, c2, ..., ck) + max(c1, c2, ..., ck).

Dave is one of the participants in this competition, and he really wants to win. So he turned to you for help, asking you to help him find the optimal cyclic route, that is, the route for which he gets the maximum number of points. Do not refuse this cute creature, help him!

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105), the number of checkpoints and the number of paths between them.

The next m lines describe the paths between checkpoints. The i-th of them contains three numbers v, u, w (1 ≤ v, u ≤ n; v ≠ u; 0 ≤ w ≤ 109), the numbers of the checkpoints that the i-th path connects, and the number of bananas on it.

Output

Print the answer to the problem: the maximum value of the sum of the minimum and maximum number of bananas over all cyclic routes. If the map has no cyclic route at all, print 0.

Examples4

Example 1
Input
```
3 3
1 2 1
2 3 1
3 1 1
```
Expected output
```
2
```
Example 2
Input
```
4 4
1 2 1
2 3 2
3 1 1
1 4 100
```
Expected output
```
3
```
Example 3
Input
```
4 5
1 2 2
2 3 1
3 1 1
1 4 2
4 2 2
```
Expected output
```
4
```
Example 4
Input
```
2 1
1 2 1
```
Expected output
```
0
```