독이 든 미로

BThero는 정점 $n$개와 간선 $n-1$개로 이루어진 트리 모양의 미로에서 탈출해야 합니다. 각 간선에는 길이가 있습니다. 정점에는 독약 병이 총 $2m$개 놓여 있으며, 독약은 $m$종류이고 종류마다 병이 2개씩 있습니다.

BThero는 어떤 정점에 처음 들어가면 그 정점의 병을 모두 즉시 마십니다. 이미 방문한 정점에 다시 들어가면 그 정점에는 마실 병이 남아 있지 않습니다.

아직 마시지 않은 종류의 독약을 마시면 중독됩니다. 해독하려면 같은 종류의 나머지 병을 찾아 마셔야 합니다.

BThero는 정점 $s$에서 출발해 그 정점의 병을 바로 마십니다. 이후 중독되지 않은 상태가 될 때까지 정점들을 지나다니고, 그 뒤에 정점 $s$로 돌아와 미로를 떠납니다.

최적의 경로를 택했을 때 BThero가 이동하는 총 거리가 가장 짧아지는 시작 정점 $s$를 구하세요.

첫 줄에 정수 $n$과 $m$이 주어집니다 ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$). 각각 정점의 수와 독약 종류의 수입니다.

다음 $n-1$개의 줄에는 정수 $u_i$, $v_i$, $w_i$가 주어집니다 ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$). 정점 $u_i$와 $v_i$를 잇는 길이 $w_i$의 양방향 간선입니다.

다음 $m$개의 줄에는 정수 $a_j$와 $b_j$가 주어집니다 ($1 \le a_j, b_j \le n$). 독약 종류 $j$의 병 두 개가 놓인 정점입니다. $a_j = b_j$일 수도 있습니다. 이 경우 BThero는 그 정점에 들어가는 순간 중독되고 바로 해독됩니다.

최적의 정점에서 출발했을 때 모든 독을 해독하기 위해 BThero가 이동해야 하는 최소 거리를 한 줄에 출력합니다.