Given a tree with nodes, conveniently numbered from to , the edge connects nodes and () with a weight of (). You can remove exactly edges from the tree to get connected components. After that, you can insert new edges with weight to connect all components to form a new tree. The edges you inserted don't have to be the same as the edges you removed. After this whole process, you want to maximize the diameter in this new tree. Can you write a program to find the longest diameter in the new tree?

#### Input Specification

The first line contains two integers, and (, ), the number of nodes and the number of edges you can remove and insert.

Each of the following lines contains three integers, , and (, ), an edge connecting nodes and with weight .

#### Output Specification

One single integer, the longest diameter in the new tree.

#### Constraints

Subtask | Points | Additional constraints |
---|---|---|

No additional constraints. |

#### Sample Input

```
5 1
1 2 3
2 3 5
2 4 -3
4 5 6
```

#### Sample Output

`14`

## Comments