#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 205, M = 5e4 + 5;
vector<ar<int, 3>> edges[2][N];
int a[M], b[M], c[M], p[M];
int d[N], par[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a[i]>>b[i]>>c[i]>>p[i];
edges[0][a[i]].push_back({b[i], c[i], i});
edges[1][b[i]].push_back({a[i], c[i], i});
}
auto djk = [&](int t, int u){
priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> q;
q.push({0, u});
for(int i=1;i<=n;i++) d[i] = 2e9;
memset(par, -1, sizeof par);
d[u] = 0;
while(!q.empty()){
int u = q.top()[1], D = q.top()[0]; q.pop();
if(D > d[u]) continue;
for(auto x : edges[t][u]){
if(d[x[0]] > d[u] + x[1]){
par[x[0]] = x[2];
d[x[0]] = d[u] + x[1];
q.push({d[u] + x[1], x[0]});
}
}
}
vector<int> tt;
for(int i=1;i<=n;i++){
if(~par[i]) tt.push_back(par[i]);
} return tt;
};
int D = 0;
vector<int> tot;
for(int t=0;t<2;t++){
vector<int> tmp = djk(t, 1);
tot.insert(tot.end(), tmp.begin(), tmp.end());
if(!t) D += d[n];
tmp = djk(t, n);
tot.insert(tot.end(), tmp.begin(), tmp.end());
if(!t) D += d[1];
}
int res = D;
auto check = [&](int in){
swap(a[in], b[in]);
for(int i=1;i<=n;i++) edges[0][i].clear();
for(int i=0;i<m;i++){
edges[0][a[i]].push_back({b[i], c[i], i});
}
int D = 0;
djk(0, 1);
D += d[n];
djk(0, n);
D += d[1];
res = min(res, D + p[in]);
swap(a[in], b[in]);
};
sort(tot.begin(), tot.end());
tot.erase(unique(tot.begin(), tot.end()), tot.end());
vector<int> is(m);
for(auto x : tot){
check(x);
is[x] = 1;
}
for(int i=0;i<m;i++){
if(is[i]) continue;
res = min(res, D + p[i]);
}
if(res >= 2e9) cout<<-1<<"\n";
else cout<<res<<"\n";
}
