#include <bits/stdc++.h> #define int long long #define pb push_back using namespace std; const int N=310; const int inf=1e18; const int mod=1e9+7; vector<array<int,3>>g[N]; int dist[N][N], dd[N]; int djikstra(int vu,int uv) { for(int i=1;i<N;i++) dd[i]=inf; set<pair<int,int>>st; dd[vu]=0; st.insert({0,vu}); while(!st.empty()) { int v=st.begin() -> second; st.erase(st.begin()); for(auto [to,w,ww]:g[v]) { if(dd[to]>dd[v]+w) { st.erase({dd[to],to}); dd[to]=dd[v]+w; st.insert({dd[to],to}); } } } return dd[uv]; } signed main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); int T=1; // cin>>T; while(T--) { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int v,u,c,d; cin>>v>>u>>c>>d; g[v].pb({u,c,d}); } for(int vu=1;vu<=n;vu++) { set<pair<int,int>>st; for(int i=1;i<=n;i++) { dist[vu][i]=inf; } st.insert({0,vu}); dist[vu][vu]=0; while(!st.empty()) { int v=st.begin() -> second; st.erase(st.begin()); for(auto [to,w,d]:g[v]) { if(dist[vu][to]>dist[vu][v]+w) { st.erase({dist[vu][to],to}); dist[vu][to]=dist[vu][v]+w; st.insert({dist[vu][to],to}); } } } } int ans=dist[1][n]+dist[n][1]; for(int v=1;v<=n;v++) { for(auto [u,c,d]:g[v]) { if(ans>min(dist[1][n],dist[1][u]+dist[v][n])+min(dist[n][1],dist[n][u]+dist[v][1])+c+d) { array<int, 3> it={u,c,d}; g[v].erase(find(g[v].begin(),g[v].end(),it)); g[u].pb({v,c,d}); ans=min(ans,djikstra(1,n)+djikstra(n,1)+d); g[u].pop_back(); g[v].pb({u,c,d}); } } } cout<<(ans < inf ? ans : -1); } }