#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const ll inf = 5e10 + 5;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
int n, m;
int A[maxn];
int B[maxn];
int C[maxn];
int D[maxn];
bool used[maxn];
const int N = 205;
vector<int> g[N];
vector<int> rg[N];
ll duz[2][N];
ll dist[2][N]; // 0 - 1, 1 - n
int from[2][N]; // 0 - 1, 1 - n
void dij1(int s, ll dist[], int from[]){
ff(i,1,n)dist[i] = inf;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({dist[s] = 0, s});
while(!pq.empty()){
pii v = pq.top(); pq.pop();
if(dist[v.se] < v.fi)continue;
for(int c : g[v.se]){
int u = B[c];
int w = C[c];
if(v.se != A[c])continue;
if(dist[u] > w + v.fi){
pq.push({dist[u] = w + v.fi, u});
from[u] = c;
}
}
}
}
ll rdist[2][N]; // 0 - 1, 1 - n
void dij2(int s, ll dist[]){
ff(i,1,n)dist[i] = inf;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({dist[s] = 0, s});
while(!pq.empty()){
pii v = pq.top(); pq.pop();
if(dist[v.se] < v.fi)continue;
for(int c : rg[v.se]){
int u = A[c];
int w = C[c];
if(dist[u] > w + v.fi){
pq.push({dist[u] = w + v.fi, u});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
cin >> n >> m;
ff(i,1,m){
int u, v, c, d;
cin >> u >> v >> c >> d;
g[u].pb(i);
rg[v].pb(i);
A[i] = u, B[i] = v, C[i] = c, D[i] = d;
}
dij1(1, dist[0], from[0]), dij1(n, dist[1], from[1]);
dij2(1, rdist[0]), dij2(n, rdist[1]);
int cur = n;
while(from[0][cur] && cur != 1){
used[from[0][cur]] = 1;
cur = A[from[0][cur]];
}
cur = 1;
while(from[1][cur] && cur != n){
used[from[1][cur]] = 1;
cur = A[from[1][cur]];
}
ll rez = dist[0][n] + dist[1][1];
ff(i,1,m){
int u = A[i];
int v = B[i];
int c = C[i];
int d = D[i];
if(!used[i]){
ll X = min(dist[0][n], dist[0][v] + c + rdist[1][u]);
ll Y = min(dist[1][1], dist[1][v] + c + rdist[0][u]);
rez = min(rez, X + Y + d);
}
else{
swap(A[i], B[i]);
g[v].pb(i);
dij1(1, duz[0], from[0]), dij1(n, duz[1], from[1]);
g[v].pop_back();
swap(A[i], B[i]);
rez = min(rez, duz[0][n] + d + duz[1][1]);
}
}
cout << (rez >= inf ? -1 : rez);
return 0;
}
/**
4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1
4 4
1 2 1 0
2 3 1 0
2 4 3 0
3 4 2 0
// probati bojenje sahovski ili slicno
**/
