#P2245. 星际导航

星际导航

题目描述

sideman\text{sideman} 做好了回到 Gliese\text{Gliese} 星球的硬件准备,但是 sideman\text{sideman} 的导航系统还没有完全设计好。为了方便起见,我们可以认为宇宙是一张有 NN 个顶点和 MM 条边的带权无向图,顶点表示各个星系,两个星系之间有边就表示两个星系之间可以直航,而边权则是航行的危险程度。

sideman\text{sideman} 现在想把危险程度降到最小,具体地来说,就是对于若干个询问 (A,B)(A, B)sideman\text{sideman} 想知道从顶点 AA 航行到顶点 BB 所经过的最危险的边的危险程度值最小可能是多少。作为 sideman\text{sideman} 的同学,你们要帮助 sideman\text{sideman} 返回家园,兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

输入格式

第一行包含两个正整数 NNMM,表示点数和边数。

之后 MM 行,每行三个整数 AABBLL,表示顶点 AABB 之间有一条边长为 LL 的边。顶点从 11 开始标号。

下面一行包含一个正整数 QQ,表示询问的数目。

之后 QQ 行,每行两个整数 AABB,表示询问 AABB 之间最危险的边危险程度的可能最小值。

输出格式

对于每个询问, 在单独的一行内输出结果。如果两个顶点之间不可达, 输出 impossible\text{impossible}

4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2
5
4
5

提示

对于 40%40\% 的数据,满足 N1000,M3000,Q1000N \leq 1000, M \leq 3000, Q \leq 1000

对于 80%80\% 的数据,满足 N10000,M105,Q1000N \leq 10000, M \leq 10^5, Q \leq 1000

对于 100%100\% 的数据,满足 $N \leq 10^5, M \leq 3 \times 10^5, Q \leq 10^5, L \leq 10^9$。数据不保证没有重边和自环。