Control chain
Rybka decided to measure criticality of Watson’s control chain, which consists of N nodes, joined by conductors. Signal can be transmitted from any node to any other node trough the only possible path. When one of nodes comes under external action, it transmits signal to every other node. That is after external action the node creates (N–1) signals. i-node intensity (iNode) of conductor is defined as product of its length to the number of signals, that go through it after external action to the node i. The conductor is considered to be i-critical, if its iNode is maximal among all other conductors (with fixed i). If several equal iNode exist, several conductors are considered to be i-critical. Total criticality of the conductor is defined as count of its i-criticalities. Criticality of complete chain is defined as maximum of total criticalities of its conductors.
Input
The first line contains one integer N – number of nodes, following (N-1) lines describe conductors, each line contains 3 integers i, j, A – describes a conductor that connects nodes i and j and has length A.
2 ≤ N ≤ 10^5, (1 ≤ i, j ≤ N, 1 ≤ A ≤ 10^5).
Output
You need to print criticality of the chain.
Hint: In the chain: 1-critical conductor 1; 2-critical: 1, 2; 3-critical: 1; 4-critical: 3; 5-critical: 4. Hence, the first conductor has 3 criticalities, so its total criticality is 3, total criticality of other conductors is 1, criticality of the chain equals to maximum of conductors’ criticalities, that is 3.