Competitions

# Breadth First Search

# Longest path in a tree

Undirected weighted tree is given. Find the length of the longest path. Find two vertices the distance between which is maximum.

#### Input

First line contains the number of vertices in the tree **n** (**2** ≤ **n** ≤ `10`

). Next ^{5}**n** - **1** lines describe the edges. Each line contains three integers: numbers of vertices connected with an edge (vertices are numbered from **1** to **n**) and the weight **w** (**1** ≤ **w** ≤ `10`

) of an edge.^{5}

#### Output

Print the length of the longest path.

Input example #1

6 1 2 3 2 3 4 2 6 2 6 4 6 6 5 5

Output example #1

12