> #include<stdio.h>
> #define inf 1000000000
> 
> struct arcnode
> {
>         int             adjvex,
>                         len,
>                         nextarc;
> }list[150000+30000+1+2];
> int pos[30000+1];
> int heap[30000+1];
> int dist[30000+1];
> int n,m,qlen;
>      
> void qup(int u)
> {   
>      int i=heap[u];
>      int p=u>>1;
>      int tmp=dist[i];
>      while(p>0&&dist[heap[p]]>tmp)
>      {
>         pos[heap[p]]=u;
>         heap[u]=heap[p];
>         u>>=1;p>>=1;
>      }
>      pos[i]=u;
>      heap[u]=i;
> }
> 
> void qdown(int root)
> {
>     int p,t=heap[root], rc;
>     while(p=(root<<1) <= qlen)
>     {
>         rc =(root<<1+1);
>         if(rc <= qlen && dist[heap[rc]] < dist[heap[p]]) p  = rc;
>         if(dist[t] > dist[heap[p]] )
>         {
>             heap[root] = heap[p];
>             pos[heap[root]] = root;
>         }
>         else break;
>         root = p;
>     }
>     heap[root] = t;
>     pos[heap[root]] = root;
> }
> 
> void dij()
> {
>       for(int i=1;i<=n;i++)
>          {
>              dist[i]=inf;
>              heap[i]=i;
>              pos[i]=i;
>          }
>          dist[1]=0;
>          qlen=n;
>          while(qlen)
>          {   
>              int min=heap[1];
>              heap[1]=heap[qlen--];
>              pos[heap[1]]=1;
>              qdown(1);
>              int h=list[min].nextarc;         
>              while(h)
>              {
>                 int w=dist[min] +list[h].len;
>                 int v=list[h].adjvex;
>                 if(dist[v]>w)
>                 {
>                     dist[v]=w;
>                     qup(pos[list[h].adjvex]);
>                }   
>                h=list[h].nextarc;
>              }
>           }
>           printf("%d\n",dist[n]);
> }
> 
> int main()
> {
>     freopen("in.txt","r",stdin);
>     int a,b,c,l,h,head;
>     while(scanf("%d %d",&n,&m)!=EOF)
>     {
>          for(int i=0,l=n+1;i<m;i++)
>          {
>              scanf("%d %d %d",&a,&b,&c);
>              h=l++;
>              list[h].adjvex=b;list[h].len=c;list[h].nextarc=0;
>              head=list[a].nextarc;
>              if(!head) 
>                 list[a].nextarc=h;
>              else
>              {
>                 while(list[head].nextarc)
>                    head=list[head].nextarc;
>                 list[head].nextarc=h;
>              }
>          }
>          dij();
>     } 
>     while(1);
>     return 0;
> }