/*
author : abushbandit
contest : ---
*/
#pragma GCC optimize("Ofast,unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int INF = 1e15,N = 500;
int dis[N + 1];
int n;
int f[N + 1][N + 1];
multiset<pair<int,int>> g[N + 1];
int dist(int x,int tar){
set<pair<int,int>> q;
for(int i = 1;i <= n;i++) dis[i] = INF;
q.insert({0, x});
dis[x] = 0;
while(!q.empty()){
auto [val,u] = *q.begin();
q.erase(q.begin());
if(val > dis[u]) continue;
for(auto [v, w] : g[u]){
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
q.insert({dis[v], v});
}
}
}
return dis[tar];
}
void solve() {
int m;
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
f[i][j] = INF;
f[i][i] = 0;
}
}
int cnt = 0;
int a[m],b[m],c[m],d[m];
for(int i = 0;i < m;i++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
cnt += c[i] == 0;
f[a[i]][b[i]] = min(c[i],f[a[i]][b[i]]);
g[a[i]].insert({b[i],c[i]});
}
for(int k = 1; k <= n; ++k){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
int ans = f[1][n] + f[n][1];
for(int i = 0;i < m;i++){
int cur = min(f[1][n], f[1][b[i]] + f[a[i]][n] + c[i]) + min(f[n][1], f[n][b[i]] + f[a[i]][1] + c[i]) + d[i];
if(cur > ans){
continue;
}
cur = d[i];
g[a[i]].erase(g[a[i]].find({b[i],c[i]}));
g[b[i]].insert({a[i],c[i]});
cur += dist(1,n) + dist(n,1);
ans = min(ans,cur);
g[a[i]].insert({b[i],c[i]});
g[b[i]].erase(g[b[i]].find({a[i],c[i]}));
}
if(ans >= INF){
ans = -1;
}
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t = 1;
//~ cin >> t;
while(t--){
solve();
}
}
