#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;
}
