콘텐츠 전송

노드가 $n$개인 컴퓨터 네트워크가 있다. 이 네트워크는 무향 트리이고, $i$번째 간선은 $a_i$번 노드와 $b_i$번 노드를 잇는다. 이 간선의 길이는 $c_i$다.

노드마다 서로 다른 데이터가 하나씩 있고, $j$번 노드에 있는 데이터의 크기는 $s_j$다. 사용자는 원하는 데이터를 원하는 노드로 전송한다. 전송 비용은 데이터 크기와 전송 거리를 곱한 값이고, 데이터는 항상 최단 경로로 이동한다.

전송이 끝나면 목적지를 포함해 경로 위의 모든 노드가 그 데이터를 캐시에 저장한다. 다음 전송부터는 그 데이터의 캐시가 있는 노드 중 목적지에서 가장 가까운 노드가 데이터를 보내므로, 비용은 원래 데이터 크기와 그 노드부터 목적지까지의 거리를 곱한 값이 된다. 처음에는 어느 노드에도 캐시가 없어서 $j$번 데이터는 $j$번 노드에만 있다.

사용자는 전송할 때마다 데이터와 목적지를 마음대로 고른다. 목적지에 이미 그 데이터의 캐시가 있으면 거리가 $0$이라서 비용도 $0$이다. 전송을 $m$번 했을 때 비용의 합이 최대 얼마인지 구하라.

첫째 줄에 노드 수 $n$과 전송 횟수 $m$이 주어진다. ($2 \le n \le 2000$, $1 \le m \le 10^9$)

다음 $n-1$개 줄에 간선의 정보가 한 줄에 하나씩 $a_i$, $b_i$, $c_i$ 순으로 주어진다. ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10000$)

다음 줄에 정수 $n$개가 주어진다. $j$번째 정수는 $j$번 노드에 있는 데이터의 크기 $s_j$다. ($1 \le s_j \le 10000$)

주어지는 네트워크는 항상 트리다.

전송을 $m$번 했을 때 얻을 수 있는 비용 합의 최댓값을 한 줄에 출력한다.