Naruto Uzumaki, the greatest ninja of all time have recently been appointed as hokage of the Leaf Village. The leaf village have n cities and n-1 bidirectional roads. Naruto knows that from each city there is a path to any other city. For simplicity, he enumerated the cities from 1 to n. Now, though The Great Ninja War ended, there are still unrest among people. So some of the roads are not safe at night, denoted by 0 or 1. So they need to be patroled.

There are n ninjas that can be assigned to each city, lets enumerate them same, 1 to n. Each ninja's job is to patrol all the road along the path from ith city to the main city, that is city 1.

Naruto wants to choose subset of such ninjas, such that if all the ninjas of the subset are chosen, all the roads can be patroled. If there are multiple numbers of such subset, you have to choose the subset containing minimum number of ninjas. Help Naruto in finding the number of ninjas in the subset.

Input Format

First line contain an integer, n (1<=n<=2*10^5)

Then n-1 follows having 3 integers u, v and x denoting there's a edge connecting u and v and x denoting if road is safe or not.

If x is 0 then road is safe and 1 denotes its unsafe.

Constraints

1<=n<=2*10^5       1<=u,v<=n         x={0,1}

Output Format

Output a single integer, the minimum number of ninjas to be choosen, so that each unsafe roads get patroled.