#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<long long, long long> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' #define ld long double #define sz(x) static_cast<int>((x).size()) #define i5 tuple<int,int,int,int,int> #define all(x) x.begin(), x.end() #define iiii tuple<int, int,int,int> #define ld long double #define lol pair<pll,pll> #define iii tuple<int,int,int> #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> int n,m; vector<vector<iii>> al(205), tal(205); vector<tuple<int,int,int,int>> ed; tuple<vector<int>,vector<int>, vector<int>> dijk(int s, int skip, vector<vector<iii>> & aa){ vector<int> pdist(n+1, 1e15), dist(n+1, 1e15), from(n+1, -1), ways(n+1, 0); pdist[s]=0; ways[s]=1; for(int i=0;i<n;i++){ pll mn=mp((int)1e16,0); for(int i=1;i<=n;i++){ mn=min(mn, mp(pdist[i], i)); } dist[mn.s]=pdist[mn.s]; pdist[mn.s]=1e15; int d=dist[mn.s], c=mn.s; for(auto [to,w,ind]:aa[c]){ if(dist[to]<d+w or pdist[to]<d+w or ind==skip)continue; if(pdist[to]==d+w or dist[to]==d+w){ ways[to]+=ways[c]; } else { ways[to]=ways[c]; assert(dist[to] == 1e15); pdist[to]=d+w; from[to]=ind; } } } return make_tuple(dist, from, ways); } signed main(){ cin>>n>>m; for(int i=0;i<m;i++){ int a,b,c,d;cin>>a>>b>>c>>d; ed.pb({a,b,c,d}); al[a].pb({b,c,i}); tal[b].pb({a,c,i}); } vector<vector<int>> anw(m+1), bnw(m+1); auto [an, af, aw] = dijk(1, m, al); auto [at, _a, _aw] = dijk(1, m, tal); auto [bn, bf, bw] = dijk(n, m, al); auto [bt, _b, _bw] = dijk(n, m, tal); vector<bool> ona(m+1, 0), onb(m+1, 0); /*for(int i=1;i<=n;i++){ printf("dist from 1 of i %lld is %lld, ways %lld, from %lld\n", i, an[i],aw[i], af[i]); }*/ int cnt=0; int ce=af[n]; while(ce != -1){ //if(cnt++ > 5)return 0; //printf("an, path ce %lld\n", ce); ona[ce]=true; anw[ce]=get<0>(dijk(1, ce, al)); bnw[ce]=get<0>(dijk(n, ce, al)); ce = af[get<0>(ed[ce])]; } ce=bf[1]; while(ce != -1){ onb[ce]=true; anw[ce]=get<0>(dijk(1, ce, al)); bnw[ce]=get<0>(dijk(n, ce, al)); ce = bf[get<0>(ed[ce])]; } int ans=an[n] + bn[1]; for(int i=0;i<m;i++){ auto [a,b,c,d]=ed[i]; // a --> b now b-->a int ab, ba; // use on forward trip int onbv=(onb[i] ? bnw[i][1] : bn[1]), elsev=(bw[b]-(bn[a]+c == bn[b]? bw[a]:0) >= 1 ? bn[b]+c+at[a] : (int)1e15); ab=(aw[b] - (an[a]+c == an[b] ? aw[a] : 0) >= 1 ? an[b] + c + d + bt[a] : (int)1e15), ba=min(onbv, elsev); ans=min(ans,ab+ba); //printf("reverse %lld to %lld (i %lld), forward ab %lld, ba %lld, onbv %lld, elsev %lld\n", a,b,i,ab,ba, onbv, elsev); // use on backwards trip ba=(bw[b] - (bn[a]+c == bn[b] ? bw[a] : 0) >= 1 ? bn[b] + c + d + at[a]: (int)1e15); ab =min((ona[i] ? anw[i][n] : an[n]), (aw[b]-(an[a]+c == an[b]? aw[a]:0) >= 1 ? an[b]+c+bt[a] : (int)1e15)); //printf("reverse %lld to %lld (i %lld), backward ab %lld, ba %lld\n", a,b,i,ab,ba); ans=min(ans, ba+ab); } cout<<(ans > 1e14? -1 : ans); }