板子

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF=0x3f3f3f3f;typedef pair
              
                pr;typedef long long ll;#define fi first#define se second#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))#define N 20000+5#define NIL -1struct node{ int next, to, w;}edge[N];int n, m, cnt;int head[N], vis[N], dist[N];struct cmp{ bool operator()(const int &a, const int &b) const { return dist[a]
               
                 s;void init(){ cnt=0; s.clear(); me(head); mem(vis); for(int i=1; i<=n; i++) dist[i]=INF;}void dijkstra(){ int v=1; s.insert(v); dist[v]=0; while(s.size()) { v=*s.begin(); s.erase(v); vis[v]=1; for(int i=head[v]; ~i; i=edge[i].next) { int t=edge[i].to; if(!vis[t] && dist[t]>dist[v]+edge[i].w) { s.erase(t); dist[t]=dist[v]+edge[i].w; s.insert(t); } } }}int main(){ int i, j, k; int u, v, w; while(cin>>n>>m) { if(!n && !m) break; init(); while(m--) cin>>u>>v>>w, add(u, v, w), add(v, u, w); dijkstra(); if(dist[n]!=INF) cout<
                
                 <