던전 크롤러

Alice와 Bob은 새로운 탈출방을 테스트하는 일을 맡았다. 이 탈출방에서 손님은 던전에 갇혀 던전 전체를 탐험해야 한다. 던전은 $n$개의 방이 정확히 $n-1$개의 통로로 연결되어 있다. 이 통로들을 따라 임의의 두 방 사이를 오갈 수 있다.

던전의 방 중 두 곳은 특별하다. 한 방에는 helix key라 불리는 보호 우상이 있다. 다른 방에는 dome trap이라는 까다로운 함정이 있는데, 이 함정은 한 번 작동하면 플레이어가 움직이지 못하게 만든다. 키를 얻기 전에 함정이 있는 방에 들어가면 플레이어는 던전에 영원히 갇힌다. 플레이어는 키가 있는 방이나 함정이 있는 방에서 시작할 수 없다.

시나리오는 $q$개 있다. $i$번째 시나리오에서 플레이어는 방 $s_i$에서 시작하고, 키는 방 $k_i$에, 함정은 방 $t_i$에 있다. 각 시나리오에 대해 함정에 갇히지 않고 던전 전체를 탐험하는 데 필요한 최소 시간을 구하라.

첫 줄에 정수 $n$과 $q$가 주어진다($3 \le n \le 2000$, $1 \le q \le 200000$). 방은 1부터 $n$까지 번호가 매겨진다. 다음 $n-1$개의 줄에는 각각 세 정수 $u$, $v$, $w$가 주어지며, 이는 방 $u$와 $v$ 사이에 통로가 있고 이를 지나는 데 $w$의 시간이 걸린다는 뜻이다($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$). 이어서 $q$개의 줄이 주어진다. $i$번째 줄에는 서로 다른 세 정수 $s_i$, $k_i$, $t_i$가 주어진다($1 \le s_i, k_i, t_i \le n$).

각 시나리오마다 모든 방을 적어도 한 번 방문하는 데 필요한 최소 시간을 출력한다. 모든 방을 적어도 한 번 방문할 수 없다면 impossible을 출력한다.