#include <ext/pb_ds/assoc_container.hpp> #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; vector<int> dijk(int s, int skip, vector<vector<iii>> & aa){ vector<int> dist(n+1, 1e15); dist[s]=0; priority_queue<pll,vector<pll>,greater<pll>> pq; pq.push({0, s}); while(!pq.empty()){ auto [d,c]=pq.top();pq.pop(); if(dist[c]<d)continue; for(auto [to,w,ind]:aa[c]){ if(dist[to]<=d+w or ind==skip)continue; dist[to]=d+w; pq.push({dist[to],to}); } } return dist; } 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<int> an, at, bn, bt; int ans=1e15; an=dijk(1, m, al), bn=dijk(n, m, al); ans=min(ans, an[n]+bn[1]); for(int i=0;i<m;i++){ auto [a,b,c,d]=ed[i]; // a --> b an=dijk(1, i, al), bn=dijk(n, i, al), at=dijk(1, i, tal), bt=dijk(n, i, tal); // use on forward trip ans=min(ans, an[b]+c+d+bt[a]+bn[1]); // use on backwards trip ans=min(ans, an[n]+bn[b]+c+d+at[a]); } cout<<(ans > 1e14? -1 : ans); }