완벽한 경로 순찰

Pleasantville은 단순함을 소중히 여기는 마을이다. Pleasantville의 도로망은 두 갈래 길로 연결된 교차점들의 모임으로 볼 수 있다. 이 도로망은 단순한 방식으로 만들어졌다. Pleasantville의 어떤 두 교차점 사이를 이동할 때 같은 길을 두 번 이상 지나지 않고 가는 방법은 정확히 하나뿐이다.

시민들은 밤에 길을 걷기 안전하도록 마을 순찰대를 조직했다. 그래서 몇몇 시민이 마을의 특정 구역을 순찰한다. 이 순찰도 단순하다. 시민 한 명은 자신에게 배정된 두 교차점 사이의 유일한 경로에 있는 모든 길을 순찰한다.

각 길 e에도 단순한 기준이 있다. 정확히 pe명의 순찰자가 길 e를 자신의 순찰 경로에 포함해야 한다. 길 e를 담당하는 순찰자가 pe명보다 적으면 안전하지 않을 수 있다. pe명보다 많으면 순찰자가 늘어난 모습에 시민들이 불안해할 수 있다.

당신은 이 마을 순찰대를 조직하는 일을 맡았다. 물론 순찰자의 수를 최소화하는 것이 이상적이다. 따라서 가능한 한 적은 순찰자를 모집하고, 각 순찰자에게 마을의 두 교차점 사이 경로를 하나씩 배정하여 어떤 길 e도 정확히 pe명의 순찰 경로에만 포함되도록 해야 한다.

그림 B.1: 첫 번째 예시를 나타낸 그림이다. 검은 실선 옆의 수는 그 길을 경로에 포함해야 하는 순찰자의 수를 나타낸다. 빨간 점선 곡선은 모든 길이 정확히 필요한 수만큼의 순찰 경로에 포함되도록 순찰 경로 10개를 고르는 한 가지 방법을 나타낸다. 즉, 한 해법은 끝점이 다음과 같은 순찰 경로 10개를 사용하는 것이다.

(5, 2),(6, 0),(6, 3),(4, 2),(4, 0),(4, 0),(4, 0),(1, 2),(2, 3),(2, 3)

각 길이 정확히 필요한 수만큼의 순찰 경로에 포함되도록 하면서 순찰자를 10명보다 적게 사용하는 것은 불가능하다.

첫째 줄에 마을의 교차점 수 N(2 ≤ N ≤ 500 000)이 주어진다. 교차점은 0부터 N − 1까지 번호가 매겨져 있다.

그다음 N − 1개 줄에 각각 세 정수 u, v, p(0 ≤ u, v < N, 0 ≤ p ≤ 109)가 주어진다. 이는 교차점 u와 교차점 v를 잇는 길이 있고, 이 길이 정확히 p개의 순찰 경로에 포함되어야 한다는 뜻이다.

주어진 길만 사용해 어떤 두 교차점 사이를 이동하는 방법은 유일하다.

마을 순찰대를 위해 모집해야 하는 순찰자의 최소 수를 나타내는 정수 하나를 한 줄에 출력한다.