1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 using namespace std; 5 #define M 20001 6 #define N 1001 7 int n,m,x,y,w1,w2; 8 int v[M],en,cnt[N],dis[N],w[M],first[M],next[M]; 9 bool inq[N];10 queue<int>q;11 void AddEdge(const int &U,const int &V,const int &W)12 {13     v[++en]=V;14     w[en]=W;15     next[en]=first[U];16     first[U]=en;17 }18 bool spfa(const int &s)19 {20     q.push(s); inq[s]=1;21     memset(dis,0x7f,sizeof(dis));22     memset(cnt,0,sizeof(cnt));23     dis[1]=0; cnt[1]=1;24     while(!q.empty())25       {26         int U=q.front();27         for(int i=first[U];i;i=next[i])28           if(dis[v[i]]>dis[U]+w[i])29             {30               dis[v[i]]=dis[U]+w[i];31               if(!inq[v[i]])32                 {33                   q.push(v[i]);34                   if((++cnt[v[i]])>n) return 0;35                   inq[v[i]]=1;36                 }37             }38         q.pop(); inq[U]=0;39       } return 1;40 }41 int main()42 {43     while(1)44       {45         scanf("%d%d",&n,&m);46         memset(v,0,sizeof(v));47         memset(w,0,sizeof(w));48         memset(first,0,sizeof(first));49         memset(next,0,sizeof(next));50         if(!n) break;51         for(int i=1;i<=m;i++)52           {53             scanf("%d%d%d%d",&x,&y,&w1,&w2);54             AddEdge(x,y,w1); AddEdge(y,x,w2);55           }56         if(spfa(1)&&dis[n]<2000000000) printf("%d\n",dis[n]);57         else puts("No such path");58       }59     return 0;60 }