#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 205;
#define int long long
const int M = 50005;
vector<pair<int,int> > A[N],B[N]; // actual and transpose
pair<int,int> edges[M];
const int inf = 1e17;
// int st[N],en[N],str[N],enr[N];
int weight[M],d[M];
int dis[4][N]; // st en str enr
int tmp[N];
int opt[2][N];
void djik(int u,int k) {
priority_queue<pair<int,int> > pq; // -w, i
pq.push({0,u});
while(!pq.empty()) {
auto [w,i] = pq.top();pq.pop();
w*=-1;
if(w>dis[k][i])continue;
for(auto [nxt,ei] : (k <= 1 ? A[i] : B[i])) {
if(dis[k][nxt] > w + weight[ei]) {
dis[k][nxt] = w + weight[ei];
if(k<=1){
opt[k][nxt] = ei;
}
pq.push({-dis[k][nxt], nxt});
}
}
}
}
void djik2(int st, int en,int exclude,map<int,int>&mp){
priority_queue<pair<int,int> > pq; // -w, i
pq.push({0,st});
for(int i = 0;i<N;i++) tmp[i]=inf;
tmp[st]=0;
while(!pq.empty()) {
auto [w,i] = pq.top();pq.pop();
w*=-1;
if(w>tmp[i])continue;
for(auto [nxt,ei] : A[i]) if(ei != exclude){
if(tmp[nxt] > w + weight[ei]) {
tmp[nxt] = w + weight[ei];
pq.push({-tmp[nxt], nxt});
}
}
}
mp[exclude]=tmp[en];
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n,m,a,b,ans=inf;
cin >> n >> m;
for(int i = 0;i<N;i++) for(int j = 0;j<4;j++)dis[j][i]=inf;
dis[0][1] = dis[2][1] = 0;
dis[1][n] = dis[3][n] = 0;
for(int i = 1;i<=m;i++) {
cin >> a >> b >> weight[i] >> d[i];
A[a].push_back({b,i});
B[b].push_back({a,i});
edges[i] = {a,b};
}
djik(1,0);
djik(n,1);
djik(1,2);
djik(n,3);
// for(int j = 0;j<4;j++) {
// for(int i = 1;i<=n;i++) cerr << dis[j][i] << " ";
// cerr << "\n";
// }
int x = n;
set<int> frontpath,backpath;
while(x!=1){
if(opt[0][x] == 0) break;
else {
int ei = opt[0][x];
x = edges[ei].f ^ edges[ei].s ^ x;
frontpath.insert(ei);
}
}
x = 1;
while(x!=n) {
if(opt[1][x] == 0) break;
else {
int ei = opt[1][x];
x = edges[ei].f ^ edges[ei].s ^ x;
backpath.insert(ei);
}
}
// for each edge in frontpath, find 1 -> n without using that edge
map<int,int> frontlen,backlen;
for(auto e : frontpath) {
djik2(1,n,e,frontlen);
}
for(auto e : backpath) {
djik2(n,1,e,backlen);
}
// for(auto e : frontpath) cerr << e << " ";
// cerr<<"\n";
// for(auto [a,b] : frontlen) cerr << a << " " << b << "\n";
int front = dis[0][n], back = dis[1][1];
ans = min(ans,front+back);
for(int i = 1;i<=m;i++) {
// st en str enr
// invert first pass: st[a] + enr[b] + w + d, if m!+ then bck
// if m in the thing then do it
int a = edges[i].f, b = edges[i].s;
if(dis[0][a] > dis[0][b])swap(a,b);
int cur = 0;
cur = dis[0][a] + dis[3][b] + weight[i] + d[i];
if(backpath.find(i) != backpath.end()) {
cur += backlen[i];
} else cur += back;
ans = min(ans, cur);
// inverst second pass
cur = dis[1][b] + dis[2][a] + weight[i] + d[i];
if(frontpath.find(i) != frontpath.end()) {
cur += frontlen[i];
}else cur += front;
ans = min(ans,cur);
}
cout << (ans >= inf ? -1 : ans);
}
