Jiry Matchings

Ruyi Ji에게는 정점이 $1$부터 $n$까지 번호로 구분되는 트리가 있고, 각 간선에는 가중치가 있다.

각 $k \le n - 1$에 대해, 간선을 $k$개 가지는 매칭 중 가중치 합이 가장 큰 값을 구한다. 간선이 $k$개인 매칭이 존재하지 않으면 "?"를 출력한다.

첫 줄에 정점의 수 $n$이 주어진다 ($2 \le n \le 200000$).

다음 $n - 1$개의 줄에는 세 정수 $u_i$, $v_i$, $w_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $-10^9 \le w_i \le 10^9$). 이는 정점 $u_i$와 $v_i$를 잇고 가중치가 $w_i$인 간선을 뜻한다. 주어지는 그래프는 트리임이 보장된다.

$n - 1$개의 정수를 출력한다. $k = 1, 2, \ldots, n - 1$개의 간선을 가지는 매칭의 가중치 합 중 최댓값이다. 해당하는 매칭이 없는 $k$에는 "?"를 출력한다.

첫 번째 입력 예에서 $k = 1$일 때는 가중치 $5$인 간선 $(2, 3)$을 고른다. $k = 2$일 때는 간선 $(2, 4)$와 $(3, 5)$를 고르며, 가중치 합은 $6$이다. 이보다 많은 간선을 가지는 매칭은 없다.