Roads of the Northern Country

Interview

Time limit1sMemory limit128 MB

Summary

Given the edges of a weighted tree of up to 10,000 cities, compute the length of the tree's diameter (the longest path between two nodes).

Level: Medium5 of 10
Topics: Tree, Graph, BFS, DFS
Solved: No attempts yet

Problem

Building roads between cities is very expensive. Therefore the northern country designed its road network so that, without visiting any city more than once, there is exactly one route between any two cities.

Every city is also reachable from every other city. Find the distance between the two cities that are farthest apart.

There can be at most 10,000 cities, numbered starting from 1.

Input

The input is given as lines until the end of file. Each line contains three positive integers u, v, and w. They mean that the distinct cities u and v are connected by a bidirectional road of length w.

Output

Print one integer: the distance between the two cities that are farthest apart.

Examples1

Example 1
Input
```
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
```
Expected output
```
22
```