#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
const ll inf = 1e18;
struct edge{
ll x, y, z, d, id;
};
struct simple{
ll x, y, id;
};
ll n, m;
edge e[50009];
vector<simple> inc[209];
vector<simple> out[209];
void dijkstra(ll beg, ll dis[], ll used[], ll dont[], vector<simple> g[], ll end, pll prt[]){
for(ll i = 1; i <= n; ++i)
dis[i] = inf;
for(ll i = 0; i < m; ++i)
used[i] = 0;
dis[beg] = 0;
priority_queue<pair<pll, pll>, vector<pair<pll, pll>>, greater<pair<pll, pll>>> pq;
pq.push({{0, beg}, {-1, -1}});
while(!pq.empty()){
int d = pq.top().ff.ff;
int v = pq.top().ff.ss;
int comeid = pq.top().ss.ff;
int comev = pq.top().ss.ss;
pq.pop();
if(dis[v] < d) continue;
if(comeid != -1)
prt[v] = {comeid, comev};
for(auto u : g[v]){
if(dont[u.id]) continue;
if(dis[u.x] > u.y + d){
dis[u.x] = u.y + d;
pq.push({{dis[u.x], u.x}, {u.id , v}});
}
}
}
if(dis[end] >= inf) return;
ll cur = end;
while(cur != beg){
used[prt[cur].ff] = 1;
cur = prt[cur].ss;
}
}
ll frombeg[2][209];
ll usedbeg[2][50009];
ll toend[2][209];
ll usedend[2][50009];
ll emptyar[50009];
ll ans[50009];
pll prt[209];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> m;
for(ll i = 0; i < m; ++i){
cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
e[i].id = i;
inc[e[i].y].pb({e[i].x, e[i].z, e[i].id});
out[e[i].x].pb({e[i].y, e[i].z, e[i].id});
ans[i] += e[i].d;
}
ll beg = 1;
ll end = n;
ll fin = 0;
dijkstra(beg, frombeg[0], usedbeg[0], emptyar, out, end, prt);
dijkstra(beg, frombeg[1], usedbeg[1], usedbeg[0], out, end, prt);
dijkstra(end, toend[0], usedend[0], emptyar, inc, beg, prt);
dijkstra(end, toend[1], usedend[1], usedend[0], inc, beg, prt);
fin += frombeg[0][end];
for(ll i = 0; i < m; ++i){
ll d = inf;
if(usedbeg[0][i] == 0){
d = min(frombeg[0][end], frombeg[0][e[i].y] + e[i].z + toend[0][e[i].x]);
ans[i] += d;
continue;
}
d = min(frombeg[1][end], frombeg[0][e[i].x]+toend[1][e[i].x]);
d = min(d, frombeg[1][e[i].y]+toend[0][e[i].y]);
ans[i] += d;
}
beg = n;
end = 1;
dijkstra(beg, frombeg[0], usedbeg[0], emptyar, out, end, prt);
dijkstra(beg, frombeg[1], usedbeg[1], usedbeg[0], out, end, prt);
dijkstra(end, toend[0], usedend[0], emptyar, inc, beg, prt);
dijkstra(end, toend[1], usedend[1], usedend[0], inc, beg, prt);
fin += frombeg[0][end];
for(ll i = 0; i < m; ++i){
ll d = inf;
if(usedbeg[0][i] == 0){
d = min(frombeg[0][end], frombeg[0][e[i].y] + e[i].z + toend[0][e[i].x]);
ans[i] += d;
continue;
}
d = min(frombeg[1][end], frombeg[0][e[i].x]+toend[1][e[i].x]);
d = min(d, frombeg[1][e[i].y]+toend[0][e[i].y]);
ans[i] += d;
}
for(ll i = 0; i < m; ++i){
fin = min(fin, ans[i]);
}
if(fin >= inf)
cout << -1;
else
cout << fin;
}
