도로

X 나라에는 $1$번부터 $N$번까지 번호가 붙은 도시가 $N$개 있다. 도로망은 양방향 일반 도로 $N-1$개로 이루어지고, 각 도로는 도시 두 곳을 이으며 길이는 양의 정수다. 도로는 모두 서로 다른 시점에 건설했다. 도로망은 어떤 두 도시 사이에도 일반 도로만 지나는 경로가 존재하도록 설계했다.

자동차 통행량이 계속 늘어나서 정부는 일반 도로를 양방향 고속도로로 교체하려고 한다. 고속도로는 다음 규칙에 따라 건설한다.

• 이미 일반 도로가 직접 놓여 있는 도시 쌍 사이에만 고속도로를 놓는다. 고속도로는 그 일반 도로를 대체한다.
• 한 시점에 공사 중인 고속도로는 하나뿐이다.
• 고속도로는 대응하는 일반 도로를 건설한 순서와 같은 순서로 건설한다.

지역은 처음 도로망의 도시와 일반 도로(고속도로는 제외한다)로 이루어진 극대 집합 중에서, 그 안의 어떤 두 도시 사이에도 일반 도로만 지나는 경로가 있는 것을 말한다. 고속도로를 하나 건설할 때마다 지역 하나가 정확히 두 지역으로 갈라진다. 새로 생긴 지역 한쪽이나 양쪽이 도로 없는 도시 하나로만 이루어질 수도 있다. 단순 경로는 같은 도시를 두 번 이상 지나지 않는 경로다.

고속도로를 하나 건설할 때마다, 새로 생긴 두 지역 각각에서 도시 두 곳을 잇는 가장 긴 단순 경로의 길이를 구하는 프로그램을 작성하라.

첫째 줄에 X 나라의 도시 수 $N$이 주어진다.

다음 $N-1$개 줄에는 고속도로를 건설하기 전의 도로망이 주어진다. 각 줄에는 양의 정수 세 개가 공백으로 구분되어 주어진다. 앞의 두 수는 일반 도로가 놓인 두 도시의 번호이고, 세 번째 수는 그 도로의 길이다.

일반 도로는 건설한 순서대로 주어진다.

$N-1$개 줄을 출력한다. $i$번째 줄에는 $i$번째 고속도로를 건설한 뒤 새로 생긴 두 지역 각각에서 도시 두 곳을 잇는 가장 긴 단순 경로의 길이를 공백으로 구분해 두 개 출력한다. 경로는 일반 도로만 사용한다. 두 수는 감소하지 않는 순서로 쓴다.

• $1 \le N \le 500000$
• 모든 일반 도로의 길이는 $1$ 이상 $1000$ 이하다.

$\{t_1, t_2, \ldots, t_k\}$는 도시 $t_1, t_2, \ldots, t_k$와 그 사이의 일반 도로로 이루어진 지역을 뜻한다. 아래 설명은 첫 번째 예제를 따라간 것이다.

1. 첫 번째 고속도로를 건설하기 전.

   

   지역은 $\{1, 2, 3, 4, 5\}$ 하나뿐이다.

2. 도시 1과 2 사이에 첫 번째 고속도로를 건설한 뒤.

   

   나라가 지역 $\{1, 5\}$와 $\{2, 3, 4\}$로 갈라진다. 각 지역에서 도시 두 곳을 잇는 가장 긴 단순 경로의 길이는 $\{1, 5\}$에서 3(도시 1과 5 사이), $\{2, 3, 4\}$에서 3(도시 3과 4 사이)이다.

3. 도시 2와 3 사이에 두 번째 고속도로를 건설한 뒤.

   

   지역 $\{2, 3, 4\}$가 $\{3\}$과 $\{2, 4\}$로 갈라진다. 두 지역의 가장 긴 단순 경로 길이는 각각 0과 2다. 이 두 수는 증가하는 순서로 출력한다.

4. 도시 2와 4 사이에 세 번째 고속도로를 건설한 뒤.

   

   지역 $\{2, 4\}$가 $\{2\}$와 $\{4\}$로 갈라진다. 두 지역의 가장 긴 단순 경로 길이는 모두 0이다.

5. 도시 1과 5 사이에 네 번째 고속도로를 건설한 뒤.

   

   지역 $\{1, 5\}$가 $\{1\}$과 $\{5\}$로 갈라진다. 가장 긴 단순 경로 길이는 모두 0이다.