#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; using ll = long long; #define int ll const int INF = (int)4e18; struct Edge { int s,e; int c,d; Edge(){}; Edge(int _u, int _v, int _c, int _d) : s(_u), e(_v), c(_c), d(_d) {}; }; bool operator < (const Edge& a, const Edge& b) { if(a.s!=b.s) return a.s < b.s; if(a.e!=b.e) return a.e < b.e; if(a.c!=b.c) return a.c < b.c; return a.d < b.d; } int n,m; set<Edge> adj[201]; vector<Edge> e; int dijkstra(int s, int e) { vector<int> dist(n+1,INF); vector<bool> seen(n+1,false); dist[s] = 0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; pq.push({0,s}); while(!pq.empty()) { auto [d,curr] = pq.top(); pq.pop(); if(dist[curr]<d||seen[curr]) continue; for(Edge r : adj[curr]) { if(d+r.c<dist[r.e]&&!seen[r.e]) { pq.push({d+r.c,r.e}); dist[r.e] = d+r.c; } } seen[curr] = true; } return dist[e]; } signed main() { cin >> n >> m; e.reserve(m); for(int i = 0; i < m; i++) { int u,v,c,d; cin >> u >> v >> c >> d; adj[u].insert(Edge(u,v,c,d)); e.push_back(Edge(u,v,c,d)); } int ans = dijkstra(1,n)+dijkstra(n,1); for(Edge r : e) { adj[r.s].erase(r); adj[r.e].insert(Edge(r.e,r.s,r.c,r.d)); ans = min(ans,r.d+dijkstra(1,n)+dijkstra(n,1)); adj[r.e].erase(Edge(r.e,r.s,r.c,r.d)); adj[r.s].insert(r); } cout << ((ans<INF)?ans:-1); return 0; }