아가멤논의 오디세이

예시 지도

미케네의 위대한 왕 아가멤논은 트로이 해안으로 원정을 떠나기 위해 아울리스에서 군대를 소집하고 있었다. 그때 아가멤논은 여신 아르테미스의 환영을 보았다. 그 환영에서 아가멤논은 자신이 아르테미스에게 바쳐진 사슴을 실수로 죽였다는 사실을 알게 되었고, 여신은 아가멤논이 트로이로 가는 항해에서 고통받게 만들겠다고 맹세했다.

아가멤논은 트로이로 향하는 길에 크레타 섬들에 들러 강력한 군대를 위한 자원을 모을 계획이었다. 아르테미스가 아가멤논이 택한 항로를 알게 된다면, 그녀는 자신의 힘으로 그 항로의 바람을 멈춰 아가멤논과 선원들을 꼼짝 못 하게 만들 것이다. 이제 아가멤논의 충실한 조언자인 당신은, 아르테미스에게 항로를 들키지 않으면서 군대가 최대한 많은 자원을 모을 수 있는 크레타 섬들 사이의 경로를 짜내야 한다.

크레타의 $N$개 섬은 $N-1$개의 항로로 서로 연결되어 있다. 각 항로에서 아가멤논은 일정량의 자원을 얻을 수 있다. 그러나 어떤 항로를 $k$번보다 많이 사용하면 아르테미스가 그 항로에서 아가멤논의 존재를 감지하고 그 항로의 바람을 멈춘다. 따라서 실행 가능한 계획은 어떤 항로도 $k$번보다 많이 사용할 수 없다.

아가멤논은 크레타의 어떤 섬에서든 출발하고 끝낼 수 있으니, 아가멤논이 얻는 자원을 최대화하는 실행 가능한 계획을 세워라. 아가멤논은 항로를 처음 사용할 때만 그 항로에서 자원을 모을 수 있다. 항로를 다시 사용할 때는 추가 자원을 얻지 못한다.

첫 번째 줄에는 두 정수 $N$ ($1 \leq N \leq 2 \cdot 10^5$)과 $k$ ($1 \leq k \leq 10^9$)가 주어진다. $N$은 크레타 섬의 수이고, $k$는 아르테미스에게 들키지 않고 한 항로를 사용할 수 있는 최대 횟수이다. 크레타의 섬들은 항로로 연결되어 있음이 보장된다.

다음 $N-1$개 줄은 항로를 설명한다. 각 줄에는 세 정수 $u, v$ ($1 \leq u, v \leq N, u \neq v$)와 $c$ ($1 \leq c \leq 10^9$)가 주어지며, 이는 항로가 섬 $u$와 $v$를 연결하고 아가멤논이 이 항로에서 $c$단위의 자원을 얻을 수 있음을 뜻한다. 모든 항로는 양방향이다. 즉, 섬 $u$에서 $v$로, 또는 섬 $v$에서 $u$로 이동하는 데 사용할 수 있다.

문제에서 설명한 실행 가능한 계획으로 아가멤논이 얻을 수 있는 최대 자원량을 한 개의 값으로 출력한다.

크레타에는 $5$개의 섬이 있고 그림과 같이 $4$개의 항로로 연결되어 있다. 첫 번째 항로는 섬 $1$과 $2$를 연결하며 아가멤논이 $3$단위의 자원을 얻을 수 있고, 나머지도 마찬가지다. 이 군도에서 아가멤논에게 가장 좋은 계획은 섬 $4$에서 출발해 섬 $1$을 방문하고($4\to1$ 항로에서 $5$단위의 자원을 얻는다), 섬 $5$에서 경로를 끝내는 것이다($1\to5$ 항로에서 $9$단위의 자원을 더 얻는다). 이렇게 하면 총 $14$단위의 자원을 얻는다.