문제

현호는 사내 네트워크 분석 업무를 담당하게 되었다. 현재 사내 네트워크는 개의 노드를 가지는 트리 형태의 네트워크인데, 이 말은 두 노드간의 연결이 정확히 개 있어서 이 연결만으로 모든 노드간에 통신을 할 수 있다는 뜻이다.

각 노드에 에서 사이의 번호를 붙이면 번째 연결은 번 노드와 번 노드를 양방향으로 연결하며, 통신에 걸리는 시간은 이다. 는 번 노드와 번 노드 사이의 거리를 나타내는데, 번 노드에서 여러 연결을 거쳐 번 노드에 도달하기 위해 걸리는 최소 시간이다. 노드를 들를 때 추가적인 작업이 없는 이상적인 시간을 따진다.

현호는 네트워크 분석을 위해 어떤 노드를 기준으로 다른 모든 노드 사이와의 거리의 합을 알고 싶다. 즉, 을 알고 싶다.

예를 들어 다음과 같이 개의 노드로 이루어진 네트워크가 있다고 하자. 각 연결 위에 적힌 수는 를 나타낸다.

번 노드를 기준으로 를 구해보면 다음과 같다.

입력

첫 번째 줄에 노드의 개수 이 주어진다.

다음 줄의 번째 줄에는 번째 연결을 나타내는 세 정수 가 주어진다.

• 주어진 개의 연결로 모든 노드가 연결되어 있다.

출력

개의 줄에 걸쳐서, 번째 줄에는 번 노드와 다른 모든 노드 사이의 거리의 합, 를 출력한다.

서브태스크