Problem C
Perfect Path Patrol

Image by paulbr75 from Pixabay

Citizens have formed a community watch program to ensure the streets are safe to walk at night. So, some citizens patrol certain regions of the neighborhood. These patrols are also simple: a single citizen simply patrols all streets lying on the unique path between two junctions assigned to them.

Each street $e$ also has a simple criterion: exactly $p_ e$ patrollers must include street $e$ in their patrol path. If fewer than $p_ e$ patrollers were assigned to cover street $e$, then it might not be safe. If more than $p_ e$ patrollers were assigned to cover street $e$, the citizens themselves might become uneasy with the heightened presence of patrollers.

You have been tasked with organizing this community watch program. Of course, it is ideal to minimize the number of patrollers you use. Thus, you must enlist the fewest possible patrollers and assign each to a path between two junctions in the neighborhood such that any street $e$ lies on exactly $p_ e$ patrollers’ paths.

Figure 1: An illustration of the first sample. The numbers by the solid black edges indicate how many patrollers must include that edge in their paths. The dashed red curves indicate one possible way to select $10$ patrol paths so every edge lies on exactly the required number of patrol paths. That is, one solution is to use $10$ patroller paths with endpoints: \[ (5, 2), (6, 0), (6, 3), (4, 2), (4, 0), (4, 0), (4, 0),(1, 2), (2, 3), (2, 3) \] It is impossible to use fewer than 10 patrollers while ensuring each street is patrolled by exactly the required number of patrol paths.

Input

The first line of input contains a single value $N$ ($2 \leq N \leq 500\, 000$) indicating the number of junctions in the neighborhood, which are numbered $0$ through $N-1$.

Then $N-1$ lines follow, each containing three integers $u,v,p$ ($0 \leq u,v < N$, $0 \leq p \leq 10^9$). This indicates there is a street connecting junction $u$ to junction $v$ and that this street must lie on exactly $p$ patrol paths.

You are guaranteed there is a unique way to travel between any two junctions using the provided streets.

Output

Output a single line with a single integer indicating the minimum number of patrollers you need to enlist for the community watch program.

7
0 1 3
1 2 5
1 3 3
0 4 7
4 5 1
4 6 2

10

5
0 1 1
0 2 1
0 3 1
1 4 1

2