레몬향의 마흐트

레몬향의 마흐트, 뎅켄의 스승이자 칠붕현 중 한 명. 그는 모든 것을 레몬으로 바꾸는 마법으로 유명하다.

대마법사 프리렌은 레몬으로 변해 버린 뎅켄의 고향을 원래대로 되돌리기 위해, 마흐트의 마법을 해주(解呪)해야 한다.

마흐트의 마법진은 $0,1,\dots,N-1$번까지 번호가 붙은 $N$개의 정점으로 이루어져 있고 루트가 $0$인 트리의 형태이다. 각 간선은 자식에서 부모로 향하는 유향 간선이다. $i$번째 간선은 $V[i]$번 정점에서 $U[i]$번 정점으로 향하는 방향의 용량 $W[i]$를 갖는 간선이다.

프리렌이 해주를 성공시키기 위해서는 모든 간선 중 최소 용량을 찾아야 한다. 즉, $W[i]$의 최솟값을 구해야 한다. 하지만 프리렌은 $N$, $U[i]$, $V[i]$만 알 뿐, $W[i]$는 알지 못한다. 따라서 그녀는 마력 조작을 통해 정보를 얻어야 한다.

마력 조작

프리렌은 최대 $200$번까지 마력 조작을 할 수 있으며, 한 번의 조작은 다음과 같이 이루어진다.

몇몇 간선을 선택하여 그 용량 $W[i]$를 $10^{10}$으로 강화한다.
각 정점에 흘려보낼 마력량을 정한다. 즉, 길이 $N$의 배열 $(F[0], F[1], \dots, F[N-1])$을 정의하고, $i$번 정점에 $F[i]$만큼의 마력을 흘려보낸다.

이때 정점 $i$에 흐르는 마력 $f(i)$는 다음과 같이 계산된다.

\[ f(i) = F[i] + \sum_{j \to i} \min \bigl(W,\, f(j)\bigr), \]

여기서 $j \to i$는 $j$에서 $i$로 향하는 간선을 의미하고, $W$는 그 간선의 용량이다.

조작이 끝난 후 프리렌은 루트 정점 $0$에 흐르는 마력 $f(0)$만을 알 수 있다. 또한 각 마력 조작은 서로 독립적으로 수행되며, 조작이 끝나면 마법진은 즉시 원상태로 복구된다.

프리렌을 도와 마흐트의 마법을 해주하기 위해, 모든 간선 중 용량의 최솟값을 찾아라.

레몬향의 마흐트

문제

마력 조작

제한