#include <bits/stdc++.h>
// Author: Ilove._.Ghibli0369
#define fi first
#define se second
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
const int mn = 2e2 + 5;
const int mod = 1000000007LL, inf = 1e18;
int n, m, kc[mn][mn], imp[mn], d1[mn], dn[mn], par[mn];
struct Egde{
int u, v, c, w;
} e[50005];
vector <int> a[mn];
void dijkstra(int u, int d[]){
for(int i = 1; i <= n; i++){
d[i] = inf;
par[i] = 0;
}
d[u] = 0;
priority_queue <pii, vector <pii>, greater<pii>> pq;
pq.push({d[u], u});
while(pq.size()){
auto [c, u] = pq.top();
pq.pop();
if(c > d[u]) continue;
for(auto i : a[u]){
if(d[e[i].v] > d[u] + e[i].c){
d[e[i].v] = d[u] + e[i].c;
par[e[i].v] = i;
pq.push({d[e[i].v], e[i].v});
}
}
}
}
void solve(){
cin >> n >> m;
fill(&kc[0][0], &kc[0][0] + mn * mn, inf);
for(int i = 1; i <= n; i++) kc[i][i] = 0;
for(int i = 1; i <= m; i++){
int u, v, c, w; cin >> u >> v >> c >> w;
a[u].push_back(i);
e[i] = {u, v, c, w};
kc[u][v] = c;
}
dijkstra(1, d1);
int cur = n;
while(cur && par[cur]){
imp[par[cur]] = 1;
cur = e[par[cur]].u;
}
dijkstra(n, dn);
cur = 1;
while(cur && par[cur]){
imp[par[cur]] = 1;
cur = e[par[cur]].u;
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
kc[i][j] = min(kc[i][j], kc[i][k] + kc[k][j]);
}
}
}
int res = d1[n] + dn[1];
for(int i = 1; i <= m; i++){
auto [u, v, c, w] = e[i];
if(!imp[i]){
res = min(res, min(kc[1][n], kc[1][v] + c + kc[u][n])
+ min(kc[n][1], kc[n][v] + c + kc[u][1]) + w);
}
else{
a[u].erase(find(all(a[u]), i));
swap(e[i].u, e[i].v);
a[v].push_back(i);
dijkstra(1, d1); dijkstra(n, dn);
res = min(d1[n] + dn[1] + w, res);
a[v].erase(find(all(a[v]), i));
swap(e[i].u, e[i].v);
a[u].push_back(i);
}
}
if(res > 1e17) res = -1;
cout << res << '\n';
}
// Waifu of the day: Persia Juliet
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if(fopen("multship.inp", "r")){
freopen("multship.inp", "r", stdin);
freopen("multship.out", "w", stdout);
}
int t = 1;
// cin >> t;
while(t--) solve();
}
