Description
冷锋在非洲完成任务后回到了狼牙特种作战部队。我们知道在战狼二结尾，冷锋正在北极执行任务，而部队发现了龙小云在c国的消息，让冷锋尽快赶往c国。我们知道现在地球上共有n个国家和地区，编号分别为1，2，3…n。国家与国家之间的可能通航班（可能不止一次），也可能没有通航班。共有m次航班，冷锋已经知道了这m次航班的信息(起点 终点，时间)北极的编号是1，c国的编号是n。
而冷峰身为超级英雄一样的的存在，他有一次将航班的时间降为零的能力。
Input
样例数t(t<=10)，接下来又t组样例。 每组样例先输入n , m(n<=1000 , m<=n*(n-1)/2)。
下面m行航班的信息，分别为start , end , time(time <= 100000).
Output
对每组样例，输出冷锋到达c国的最短时间，若不能到达输出 “Impossible”。
Sample Input
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
Sample Output
Impossible
4
0
一开始 没想那么多，就想着求出来1-n最短路，然后路径还原，找到其中的最大边，将其减掉就是答案。 然后无限wa.。 最后才发现，可能会有别的1-n的路，虽然不是最短路到达n，但是去掉其的最大边，1-n最短路更小。 然后我就不会写了 TAT 。
然后就看了题解，没想到是枚举边，照着思路写了一发就A了，哎~
看代码吧
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;const int MAXN = 1e3+10 ;
const int MAXM = 1e6+10;
const int mod = 1e9+7 ;
const int inf = 0x3f3f3f3f;struct Edge {int from,to,val,next;
}edge[MAXM];
int head[MAXN],top;
int n,m;
void init(){memset(head,-1,sizeof(head));top=0;
}
void addedge(int a,int b,int c){Edge e={a,b,c,head[a]};edge[top]=e;head[a]=top++;
}void getmap(){while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);addedge(b,a,c);}
}int dis1[MAXN],dis2[MAXN],vis[MAXN];
void spfa(int st ,int *dis){for(int i=1;i<=n;i++){dis[i]=inf;vis[i]=0;}vis[st]=1;dis[st]=0;queue<int>Q;Q.push(st);while(!Q.empty()){int now=Q.front();Q.pop();vis[now]=0;for(int i=head[now];i!=-1;i=edge[i].next){Edge e=edge[i];if(dis[e.to]>dis[now]+e.val){dis[e.to]=dis[now]+e.val;if(!vis[e.to]) {vis[e.to]=1;Q.push(e.to);}}}}
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();getmap();spfa(1,dis1);spfa(n,dis2);int ans=inf; for(int i=0;i<top;i+=2){
// 因为不确定 一条边，哪头是正向或者是反向 ，所以要都求一下 。Edge e=edge[i];ans=min(ans,min(dis1[e.from]+dis2[e.to],dis1[e.to]+dis2[e.from]));}if(ans==inf)puts("Impossible");else printf("%d\n",ans); }return 0;
}