题目描述

Alice 和 Bob 目前负责测试一个密室！在这个密室中，玩家被困在一个地下城中，他们必须探索整个区域。这个地下城包含被恰好 $n-1$ 条通道连接的 $n$ 个房间，使用这些通道可以在任意一对房间之间通行。

地下城中的两个房间是特殊的。其中一个房间有一个名为「螺旋钥匙」的守护神像，另一个不同的房间有一个讨厌的「圆顶陷阱」，一旦被激活，玩家就无法移动了。在获得钥匙之前进入有陷阱的房间将导致玩家永远被困在地牢里。玩家不能从有钥匙或陷阱的房间出发。

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。

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

15
17
impossible
12

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

11
impossible
10
10