> #include<stdio.h>
> #include<stdlib.h>
> #include<string.h>
> struct node{
>    int val,ver;
>    struct node *next;
> }; 
> struct Graph{
>     node *h;
> }G[30005]; 
> char f[30005];
> int min[30005],n;
> node *p;
> int MIN(int s,int e)
> {  int u,v,M,j,i;
>    //memset(f,0,sizeof(f));
>    //memset(min,0,sizeof(min)); 
>    for(p=G[s].h;p!=NULL;p=p->next)
>    { min[p->ver]=p->val;}
>    f[s]=1;
>    for(j=1;j<n;j++)
>    {
>       M=2000000000;
>       for(i=1;i<=n;i++)
>       { if(min[i]==0)continue;
>         if(f[i]==0&&min[i]<M)
>         {  M=min[i];v=i;} 
>       }            
>       if(v==e)return M;
>       f[v]=1;if(M==2000000000) break;
>       for(p=G[v].h;p!=NULL;p=p->next)
>       {
>          u=p->ver;
>          if(f[u]==0)
>          { if((p->val + M)<min[u]||min[u]==0)
>               min[u]=p->val+M;
>          }    
>       }
>    }  
> }     
> int main()
> {
>    int i,j,m,k,t,a,b,c;   
>    while(1)
>    {
>       scanf("%d%d",&n,&m);
>       for(i=1;i<=n;i++)G[i].h=NULL;
>       for(i=1;i<=m;i++)
>       {
>          scanf("%d%d%d",&a,&b,&c);
>          p=(node *)malloc(sizeof(node));
>          p->val=c;p->ver=b;p->next=G[a].h;
>          G[a].h=p;
>       }   
>       a=MIN(1,n);
>       printf("%d\n",a);
>       break;
>    }
> }