URI Online Judge | 2103

Harbin is Too Much Money!

By XIII Maratona de Programação IME-USP, 2009 BR Brazil

Timelimit: 1

Harbin is an organized city, but constructed in a very economic way. All the streets are two-way streets, and it's possible to go from one point of the city to any other point, always walking through paved streets, but there are not two differents paths of paved streets connecting any two different points of the city. The mayor responsible for paving the streets claims he applied some sort of holand algorithm, but no one ever understood the name of the algorithm, so no one knows if it's true or not.

At the time of the ice statues festival in Harbin the statues are spread in several points of the city, and the tourists are invited to walk through the paved streets in order to visit all of it. Always thinking about economy, the mayor wants to know what is the total length, in kilometers, of the paths that connects all of the pairs of statues (each pair must be counted only once, in other words, if you have already counted the path from A to B, you shouldn't count the path from B to A). Your task in this problem is, given the position of the statues and the lenghts of the paved streets that connect the statues, determine this total length.

Input

The input is composed of several instances. The first input row of each instance contains an integer N (1 ≤ N ≤ 10000), representing the number of statues. The statues are enumerated from 1 to N. Each one of the following N-1 rows contains three integers A, B and C (1 ≤ A, BN, 1 ≤ C ≤ 50), indicating that the paved street that connects the statues A and B has length C.

Output

For each instance print the sum of lenghts of the paths that connects all the pairs (not-ordered) of statues.

The answer must be in MOD1300031.

Sample Input Sample Output

2
3
1 2 1
1 3 1
3
1 2 2
2 3 1

4
6