ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2005 Round I

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Cargo Agency

Time limit: 1.0 second
Memory limit: 64 MB
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, jN and ij.


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, biN) 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
To submit the solution for this problem go to the Problem set: 1371. Cargo Agency