물류 창고

ICP(International Carrier Products) 회사는 제품 배송을 효율적으로 하기 위해 새로운 물류 창고 $k$개를 지으려고 한다. 제품은 목적지로 배송되기 전에 물류 창고에 보관되고, 그곳에서 최종 유통 지점으로 배송된다. 물류 창고의 위치는 배송 시간과 창고 공간에 큰 영향을 준다.

공급망을 트리 $T = (V, E)$로 생각해 보자. 각 노드 $v_i$의 가중치는 $w_i$이고, 각 간선 $e_j$의 길이는 정수 $l_j$이다. 간선 위의 점 $p$에 대해 노드 $v_i$에서 $p$까지의 거리는 $w_i \times |\pi(v_i, p)|$로 정의한다. 여기서 $\pi(v_i, p)$는 $T$에서 $v_i$와 $p$를 잇는 경로이고, $|\pi(v_i, p)|$는 그 경로에 있는 구간(간선)의 길이 합이다.

이 제약 아래에서 $T$의 간선 위에 중심 $k$개를 고른다. 간선 $e$ 위의 중심은 $e$의 각 끝점에서 정수 거리에 있어야 한다. 중심은 노드 위에 놓여도 된다. 예를 들어 간선 $e$의 길이가 3이면, 두 끝점과 각 끝점에서 거리 1인 두 점, 총 네 점 중에서 중심을 고를 수 있다.

목표는 어떤 노드에서든 가장 가까운 중심까지의 거리 중 최댓값이 최소가 되도록 중심 $k$개를 고르는 것이다. 이렇게 고른 중심 $k$개의 집합을 최적 중심 집합이라고 한다.

그림 (a)는 가중치가 3, 3, 1, 2인 노드 네 개와 길이가 2, 3, 2인 간선 세 개로 이루어진 트리이다. 중심은 노드 위나 작은 회색 사각형 위에 놓을 수 있다. 중심을 세 개 고르면 최적해는 그림 (b)의 검은 사각형과 같으며, 이때 최대 거리는 2이다.

(a)	(b)

첫 줄에는 두 정수 $n$과 $k$($1 \le k \le n \le 200,000$)가 주어진다. $n$은 트리의 노드 수이고, $k$는 고를 중심의 개수이다. 이어서 $n-1$개의 간선이 주어진다. 노드는 1부터 $n$까지, 간선은 1부터 $n-1$까지 번호가 매겨져 있다.

다음 줄에는 양의 정수 $n$개가 주어지며, $i$번째 정수는 $i$번째 노드의 가중치이다. 가중치는 $10^6$ 이하이다.

이후 $n-1$개의 줄에는 각각 양의 정수 세 개가 주어진다. 처음 두 정수는 $i$번째 간선의 양 끝 노드 번호이고, 세 번째 정수는 그 간선의 길이이다. 길이는 $10^6$ 이하이다.

최적 중심 집합에서 노드로부터 가장 가까운 중심까지의 거리의 최댓값을 한 줄에 출력한다.