问题 B: 紧急营救

问题 B: 紧急营救

时间限制: 1 Sec  内存限制: 128 MB
提交: 162  解决: 37
[状态] [讨论版] [提交] [命题人:]
题目描述
冷锋在非洲完成任务后回到了狼牙特种作战部队。我们知道在战狼二结尾，冷锋正在北极执行任务，而部队发现了龙小云在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
[提交][状态]