Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Submit All submissions Best solutions PDF Back to list

EILOCAL2 - Local Area Network (Easy)

Local Area Network (LAN) needs multiple Switches. The tranmission time is proportional to the length of the wire (skip the role of Switch). Find the longest distance from the Internet Network Provider (ID 0) to a customer.

Input

The first line is an integer N (1<=N<=10^5) - the number of switches

 

N-1 next lines each contains three integers u, v and w which denote switch u is connected to switch v by cable with length w (1<=w<10^5, 0<=u,v<n)

N-1 next lines each contains three integers u, v and w which denote switch u is connected to switch v by cable with length w (1<=w<10^5, 0<=u,v<n)

 

Output

Print out the longest tranmission distance from the network provider

Example

Input:
4
0 1 2
0 2 2
0 3 3
Output:
3

Input:
5
0 1 2
0 2 2
0 3 3
2 4 2
Output:
4
Submit solution!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.