#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 = 1e18 + 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;
array<int,4> niz[maxn];
const int N = 105;
vector<array<int,3>> g[N];
vector<pii> rg[N];
bool used[N];
ll dist[2][maxn]; // 0 - 1, 1 - n
int from[2][maxn]; // 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(auto c : g[v.se]){
int u = c[0];
int w = c[1];
int id = c[2];
if(dist[u] > w + v.fi){
pq.push({dist[u] = w + v.fi, u});
from[u] = id;
}
}
}
}
ll rdist[2][maxn]; // 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(auto c : rg[v.se]){
int u = c.fi;
int w = c.se;
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({v, c, i});
rg[v].pb({u, c});
niz[i] = {u, v, c, 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 = niz[from[0][cur]][0];
}
cur = 1;
while(from[1][cur] && cur != n){
used[from[1][cur]] = 1;
cur = niz[from[1][cur]][0];
}
ll rez = inf;
ff(i,1,m){
int u = niz[i][0];
int v = niz[i][1];
int c = niz[i][2];
int d = niz[i][3];
if(!used[i]){
ll A = min(dist[0][n], dist[0][v] + c + rdist[1][u]);
ll B = min(dist[1][1], dist[1][v] + c + rdist[0][u]);
rez = min(rez, A + B + d);
}
}
rez = min(rez, dist[0][n] + dist[1][1]);
cout << (rez == inf ? -1 : rez) << endl;
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
**/
