Description

Xiao Q recently learned some graph theory. According to the textbook, we have the following definitions. A tree is an undirected graph that is connected and acyclic, where each edge has a positive integer weight representing its length. If a tree has $N$ nodes, it can be shown that it has exactly $N-1$ edges.

Path: In a tree, between any two nodes there exists at most one simple path. We use $\text{dis}(a,b)$ to denote the sum of the lengths of the edges on the path between $a$ and $b$. We call $\text{dis}(a,b)$ the distance between nodes $a$ and $b$.

Diameter: In a tree, the longest path is called the diameter of the tree. The tree’s diameter may not be unique.

Now Xiao Q wants to know, for a given tree, what the length of its diameter is, and how many edges are traversed by all diameters.

Input Format

The first line contains an integer $N$, the number of nodes.

The next $N-1$ lines each contain three integers $a,b,c$, indicating there is an undirected edge of length $c$ between nodes $a$ and $b$.

Output Format

Output two lines. The first line contains one integer, the length of the diameter. The second line contains one integer, the number of edges that are traversed by all diameters.

6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100

1110 
2

Hint

[Sample Explanation]

There are two diameters: the path from $3$ to $2$ and the path from $3$ to $6$. Both diameters pass through edge $(3,1)$ and edge $(1,4)$.

For $100\%$ of the testdata: $2 \le N \le 2 \times 10^5$, $1 \le a,b \le N$, $0 \le c \le 10^9$. The input graph forms a tree.

Translated by ChatGPT 5