P9440 [ICPC 2021 WF] Dungeon Crawler

有一棵 $n$ 个结点的树，边带权。你可以从一个结点通过边移动到一个相邻的结点，花费等同于边权的时间。 其中，有两个特殊结点，一个结点里有钥匙，一个结点里有陷阱。你只有先获得钥匙，才能进入陷阱所在的结点。 现有 $q$ 组询问，在第 $i$ 组询问中，你要从第 $s_i$ 号结点出发，钥匙在第 $k_i$ 号结点，陷阱在第 $t_i$ 号结点。你需要对于每组询问回答遍历整棵树所需的最短时间。题目保证你不会在钥匙所在的结点或者陷阱所在的结点出发。如果不可能遍历整棵树，输出 `impossible`。

第一行两个整数 $n,q$，含义如题目所述。 接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示有一条连接结点 $u,v$，权值为 $w$ 的边。 接下来 $q$ 行，每行三个整数 $s_i,k_i,t_i$，含义如题目所述。 $3\le n\le 2000$，$1\le q \le 2\times10^5$，$1\le u,v\le n,u\ne v$，$1\le w\le 10^9$，$1\le s_i,k_i,t_i\le n$。

对于每组询问，输出一行，包含一个整数表示答案，或者输出 `impossible` 表示无解。