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

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

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

어떤 참가자의 최종 점수를 최대화하는 방법의 하나로는 어떤 지점에서 점수가 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을 구하는 프로그램을 작성하라.

점수 경주 timer 6.5s memory 1024MB

점수 경주 6.5s 1024MB