> 我跑的是spfa
> #include<stdio.h>
> #include<string.h>
> #include<iostream>
> #include<algorithm>
> #include<math.h>
> #include<set>
> #include<stack>
> #include<vector>
> #include<map>
> #include<queue>
> #define myself i,l,r
> #define lson i<<1
> #define rson i<<1|1
> #define Lson i<<1,l,mid
> #define Rson i<<1|1,mid+1,r
> #define half (l+r)/2
> #define inff 0x3f3f3f3f
> #define lowbit(x) x&(-x)
> #define PI 3.14159265358979323846
> #define min4(a,b,c,d) min(min(a,b),min(c,d))
> #define min3(x,y,z) min(min(x,y),min(y,z))
> #define pii make_pair
> #define pr pair<int,int>
> const int dir[4][2]={0,1,0,-1,1,0,-1,0};
> typedef long long ll;
> const ll inFF=9223372036854775807;
> typedef unsigned long long ull;
> using namespace std;
> const int maxn=1e5+5;
> int head[maxn],sign;
> int d[maxn],vis[maxn];
> int n,m;
> struct node
> {
>     int to,p,val;
> }edge[maxn];
> void add(int u,int v,int val)
> {
>     edge[sign]=node{v,head[u],val};
>     head[u]=sign++;
> }
> void init()
> {
>     sign=0;
>     memset(head,-1,sizeof(head));
> }
> int spfa()
> {
>     for(int i=0;i<=n;i++)
>     {
>         d[i]=0;
>         vis[i]=0;
>     }
>     d[1]=inff;
>     queue<int> q;
>     q.push(1);
>     while(!q.empty())
>     {
>         int u=q.front();
>         q.pop(),vis[u]=0;
>         for(int i=head[u];~i;i=edge[i].p)
>         {
>             int v=edge[i].to;
>             if(d[v]<min(edge[i].val,d[u]))
>             {
>                 d[v]=min(edge[i].val,d[u]);
>                 if(!vis[v])
>                 {
>                     q.push(v);
>                     vis[v]=1;
>                 }
>             }
>         }
>     }
>     return d[n];
> }
> int main()
> {
>     int t,x,y,z,p=0;
>     cin>>t;
>     while(t--)
>     {
>         scanf("%d %d",&n,&m);
>         init();
>         for(int i=1;i<=m;i++)
>         {
>             scanf("%d %d %d",&x,&y,&z);
>             add(x,y,z),add(y,x,z);
>         }
>         printf("Scenario #%d:\n",++p);
>         cout<<spfa()<<endl;
>         printf("\n");
>     }
>     return 0;
> }