Advanced Carriage Messaging company does business in cargo delivery, so it has a complicated network of branch offices. Business is successfull, and it was decided to establish new offices to extend further the delivery network. But first of all company management department wants to analyze the efficiency of delivery between offices. You were asked to do this analysis, because of your renowned experience and knowledge.
Delivery works in the following way. There exists exactly one route of cargo delivery from any office to another office (possibly via intermediate ones). The times t[i, j] of cargo delivery between two offices (with numbers i and j) have been measured. These times are available only for offices which have direct communication. Direct cargo delivery for other offices is impossible. You are asked to calculate the average delivery time between offices, i.e. the following value:
sum (t[i, j]) / (N*(N − 1)), where the sum is taken for 1 ≤ i, j ≤ N and i ≠ j.
The first line of input contains one integer N (2 ≤ N ≤ 50000) — the number of branch offices of ACM company. Each of next N−1 lines contains three numbers ai, bi, ci. Numbers ai, bi (1 ≤ ai, bi ≤ N) are numbers of offices which have a direct communication between them. Integer number ci (0 ≤ ci ≤ 1000) is a cargo delivery time between these offices.
Output must contain a single number: average cargo delivery time between branch offices of ACM company with a precision of 4 decimal digits.
1 2 1
2 3 1
2 4 1
Problem Author: Aleksandr Klepinin (idea by Den Raskovalov)
Problem Source: IX Urals Programming Contest. Yekaterinburg, April 19-24, 2005