점수 경주

KOI 공원은 $1$번 지점부터 $N$번 지점까지 $N$개의 지점으로 구성되어 있으며, 두 지점을 잇는 $N - 1$개의 도로가 있다. $i$번째 도로는 $U\_i$번 지점과 $V\_i$번 지점을 이으며, 점수 $W\_i$를 가진다($1 \le i \le N - 1$).

KOI 공원에서는 어떤 두 지점이든 도로를 따라 서로 이동할 수 있다. 즉, KOI 공원은 트리 구조를 이룬다.

KOI 공원에서 점수 경주를 하려고 한다. 점수 경주는 다음과 같이 이루어진다.

• 총 $N - 1$명의 참가자가 시작 지점에서 출발해, 각자 시작 지점을 제외한 서로 다른 $N - 1$개의 지점으로 단순 경로를 따라 이동한다.
• 각 참가자는 처음에 $0$점의 점수를 가지고 있다.
• 각 도로에 대해, 해당 도로를 지나면 그 도로의 점수만큼 점수를 받게 된다.
• 참가자들은 어떤 지점에서든 자신의 점수를 $0$점으로 만들 수 있다. 자신의 목표 지점으로 도착한 후에도 가능하다.

어떤 참가자의 최종 점수를 최대화하는 방법의 하나로는 어떤 지점에서 점수가 $0$점 미만이 될 때마다 $0$점으로 바꾸는 방법이 있다. 이를 최적 전략이라고 하자. 참가자들은 모두 최적 전략을 따르기로 하였다.

$i$번 지점에 대해, 해당 지점이 시작 지점일 때 최적 전략을 따랐을 때 참가자들의 최종 점수의 총합을 $S\_i$라고 하자. 또한 그때 참가자들이 자신의 점수를 $0$점으로 바꾼 횟수의 총합을 $C\_i$라고 하자.

예를 들어, KOI 공원의 모습이 다음과 같을 때, $1$번 지점이 시작 지점인 경우를 생각해 보자.

최적 전략을 따를 때, 점수 경주의 과정은 다음과 같다.

• $2$번 지점이 목표 지점인 참가자는 $2$번 지점으로 이동하며 $-1$점을 받게 된다. 이후 $2$번 지점에서 자신의 점수를 $0$점으로 만든다. 최종 점수는 $0$점이다.
• $3$번 지점이 목표 지점인 참가자는 $3$번 지점으로 이동하며 $2$점을 받게 된다. 최종 점수는 $2$점이다.
• $4$번 지점이 목표 지점인 참가자는 $2$번 지점으로 이동하며 $-1$점을 받는다. 이후 $2$번 지점에서 자신의 점수를 $0$점으로 만든다. 이후 $4$번 지점으로 이동하며 $2$점을 받게 된다. 최종 점수는 $2$점이다.
• $5$번 지점이 목표 지점인 참가자는 $3$번 지점으로 이동하며 $2$점을 받는다. 이후 $5$번 지점으로 이동하며 $-3$점을 받는다. 이후 $5$번 지점에서 자신의 점수를 $0$점으로 만든다. 최종 점수는 $0$점이다.
• $6$번 지점이 목표 지점인 참가자는 $3$번 지점으로 이동하며 $2$점을 받는다. 이후 $6$번 지점으로 이동하며 $-1$점을 받게 된다. 최종 점수는 $1$점이다.

따라서 $S\_1 = 5$, $C\_1 = 3$이다.

$S\_1,\cdots,S\_N$ 및 $C\_1,\cdots,C\_N$을 구하는 프로그램을 작성하라.

첫 번째 줄에 $N$이 주어진다.

이후 $N - 1$개의 줄에 걸쳐 $i$번째 줄에는 $U\_i$, $V\_i$, $W\_i$가 공백으로 구분되어 주어진다.

$S\_1,\cdots,S\_N$만을 구한 경우

• 첫 번째 줄에 $0$을 출력한다.
• 두 번째 줄에 $S\_1, \cdots, S\_N$을 공백으로 구분하여 출력한다.

$S\_1, \cdots, S\_N$ 및 $C\_1,\cdots,C\_N$을 구한 경우

• 첫 번째 줄에 $1$을 출력한다.
• 두 번째 줄에 $S\_1, \cdots, S\_N$을 공백으로 구분하여 출력한다.
• 세 번째 줄에 $C\_1, \cdots, C\_N$을 공백으로 구분하여 출력한다.

• 주어지는 모든 수는 정수이다.
• $2 \le N \le 300\\,000$
• $1 \le U\_i, V\_i \le N$ $(1 \le i \le N - 1)$
• $-10\\,000\\,000 \le W\_i \le 10\\,000\\,000$ $(1 \le i \le N - 1)$