Alice 和 Bob 负责测试一个新的密室逃脱游戏！在这个密室中，顾客被困在地牢里，必须探索整个区域。地牢由 $n$ 个房间组成，这些房间由恰好 $n-1$ 条走廊连接。通过这些走廊，可以在任意两个房间之间通行。

地牢中有两个特殊的房间。其中一个房间里有一个被称为“螺旋钥匙”（helix key）的保护性偶像。另一个房间里有一个讨厌的“圆顶陷阱”（dome trap），一旦激活，玩家将无法移动。在获得钥匙之前进入有陷阱的房间，会导致玩家永远被困在地牢中。玩家不能从钥匙所在的房间或陷阱所在的房间开始。

Alice 和 Bob 希望考察 $q$ 种不同的场景。在第 $i$ 个场景中，玩家从房间 $s_i$ 出发，钥匙在房间 $k_i$，陷阱在房间 $t_i$。对于每个场景，计算在不被困住的情况下探索整个地牢所需的最短时间。

螺旋钥匙

输入格式

输入的第一行包含两个整数 $n$ 和 $q$，其中 $n$ ($3 \le n \le 2\,000$) 是房间的数量，$q$ ($1 \le q \le 200\,000$) 是需要考虑的场景数量。房间编号从 $1$ 到 $n$。接下来的 $n-1$ 行，每行包含三个整数 $u$、$v$ 和 $w$，表示房间 $u$ 和 $v$ 之间有一条走廊（$1 \le u, v \le n, u \neq v$），通行时间为 $w$ ($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。

样例

输入 1

5 4
1 2 3
1 3 1
3 4 4
3 5 2
1 2 4
1 4 2
5 2 1
4 3 1

输出 1

15
17
impossible
12

输入 2

7 4
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 2 3
5 4 1
3 1 4
2 4 5

输出 2

11
impossible
10
10