Maximum sum of paths P36665

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 \le n \le 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.