问题 B: 紧急营救

问题 B: 紧急营救

时间限制: 1 Sec  内存限制: 128 MB
提交: 162  解决: 41
[状态] [讨论版] [提交] [命题人:]
题目描述
冷锋在非洲完成任务后回到了狼牙特种作战部队。我们知道在战狼二结尾,冷锋正在北极执行任务,而部队发现了龙小云在c国的消息,让冷锋尽快赶往c国。我们知道现在地球上共有n个国家和地区,编号分别为1,2,3...n。国家与国家之间的可能通航班(可能不止一次),也可能没有通航班。共有m次航班,冷锋已经知道了这m次航班的信息(起点 终点,时间)北极的编号是1,c国的编号是n。
而冷峰身为超级英雄一样的的存在,他有一次将航班的时间降为零的能力。
输入

样例数t(t<=10),接下来又t组样例。 每组样例先输入n , m(n<=1000 , m<=n*(n-1)/2)。

下面m行航班的信息,分别为start , end , time(time <= 100000).表示start和end两地可以互相到达。
输出
对每组样例,输出冷锋到达c国的最短时间,若不能到达输出 "Impossible"。
样例输入 Copy
3
3 1
1 2 1
4 3
1 2 4
2 3 1
2 4 4
3 3
1 2 100000
2 3 1
1 3 2
样例输出 Copy
Impossible
4
0