You are given a tree with *n* nodes,
where each edge has a positive cost.
Let *x* and *y* be any two adjacent nodes.
Define *p*(*x*, *y*) as the maximum cost of all paths (with no repeated nodes)
whose first step goes from *x* to *y*.
Define *c*(*x*) as the sum of *p*(*x*, *y*) for all *y* adjacent to *x*.
Please compute the maximum value of *c*(*x*) among all nodes *x*.

**Input**

Input consists of several cases.
Every case begins with the number of nodes *n*,
followed by *n*−1 edges,
each one with two different nodes and the cost of the edge between them.
Assume 2 ≤ *n* ≤ 10^{5}.
The nodes are numbered starting at zero.
Each cost is an integer number between 1 and 1000.
The given graph is always a tree.
The number of steps between any two nodes is never larger than 1000.

**Output**

For every case, print the maximum *c*(*x*),
and how many nodes *x* achieve such a value.

Public test cases

**Input**

2 0 1 100 3 1 0 10 1 2 20 4 1 0 10 1 2 20 3 1 30 6 0 2 20 1 2 50 2 3 100 3 4 30 3 5 40

**Output**

100 2 30 3 60 1 220 1

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Desè Concurs de Programació de la UPC - Final
- Date
- 2012-09-15