> #include <iostream>  
> #include <queue>  
> using namespace std;  
> const long lmax = 1000000000;  
> const long edge_maxn = 30005;  //边的最大上限  
> const long point_maxn = 1500005;   //点的最大上限  
> struct node  
> {/*node存储边，一个edge代表一条边*/  
>     int v;     //终点位置  
>     int w;     //权值  
>     int next;  //同一起点的下一条边存储在edge数组中的位置
> }edge[edge_maxn];  
> int pre[point_maxn];  //以该点为起点的第一条边存储在edge数组中的位置  
> int n;  //点的数量  
> int m;  //边的数量  
> queue<int> Q;  
> int dirs[point_maxn];  
> bool vis[point_maxn];  
> void Init()  
> {  
>     memset(pre,-1,sizeof(pre));  
>     int Index = 1;  
>     int i,j,flag;  
>     int x,y,w;  
>     for(i=0;i<m;i++)  
>     {  
>         scanf("%d%d%d",&x,&y,&w);  
>         for(flag=0,j=pre[x];j!=-1;j=edge[j].next)  
>         {//重边的情况  
>             if(y == edge[j].v)  
>             {  
>                 if(w < edge[j].w)  
>                     edge[j].w = w;  
>                 flag = 1;  
>                 break;  
>             }  
>         }         
>         if(flag == 1)  
>             continue;  
>         edge[Index].v = y;  
>         edge[Index].w = w;  
>         edge[Index].next = pre[x];  //保存x起点的上一条边在edge数组中的位置  
>         pre[x] = Index++;  //位置更新  
>     }  
> }  
> void print(int end)  
> {  
>     printf("%d\n",dirs[end]);  
> }  
> void SPFA()  
> {  
>     int start = 1;  
>     int end = n;    
>     while(!Q.empty())  
>     {  
>         Q.pop();  
>     }  
>     memset(vis,0,sizeof(vis));    //初始每个点的访问记录
>     fill(dirs,dirs+point_maxn,lmax);  
>       
>     dirs[start] = 0;  
>     vis[start] = 1;  
>     Q.push(start);  
>     while(!Q.empty())  
>     {  
>         int top = Q.front(); //边的起点  
>         Q.pop();  
>         vis[top] = 0;  
>         for(int j=pre[top];j!=-1;j=edge[j].next)  
>         {  
>             int e = edge[j].v; //边的终点  
>             if(dirs[e] > edge[j].w + dirs[top])  
>             {  
>                 dirs[e] = edge[j].w + dirs[top];  
>                 if(!vis[e])  
>                 {  
>                     Q.push(e);  
>                     vis[e] = 1;  
>                 }  
>             }  
>         }  
>     }  
>     print(end);  
> }  
> int main()  
> {  
>     while(scanf("%d%d",&n,&m)!=EOF )  
>     {  
>         Init();  
>         SPFA();  
>     }  
>     //system("pause");  
>     return 0;