#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
typedef pair<ll, pair<int, int>> pii2;
struct st{int a, b; ll c, d;} kraw[50005];
vector<pii2> g2[205];
ll odl2[2][205]; //0. to z 1 do innych, 1. to z n do innych, 2. to z innych do 1, 3. to z innych do n
void dijkstra2(int s, int b, int BL){
priority_queue<pii> pq;
pq.emplace(0, s);
odl2[b][s] = 0;
while(!pq.empty()){
int x = pq.top().ss; ll dis = -pq.top().ff;
pq.pop();
for(pii2 u : g2[x]){
if(u.ss.ss == BL) continue;
if(odl2[b][u.ss.ff] > dis + u.ff){
odl2[b][u.ss.ff] = dis + u.ff;
pq.emplace(-odl2[b][u.ss.ff], u.ss.ff);
}
}
}
}
int main(){
int n, m, a, b; ll c, d;
scanf("%d%d", &n, &m);
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= n; ++j) odl2[0][i] = odl2[1][i] = 1e18;
for(int i = 0; i < m; ++i){
scanf("%d%d%lld%lld", &a, &b, &c, &d);
kraw[i] = {a, b, c, d};
g2[a].push_back({c, {b, i}});
}
ll wynik = 1e18;
for(int i = 0; i < m; ++i){
a = kraw[i].a, b = kraw[i].b, c = kraw[i].c, d = kraw[i].d;
g2[b].push_back({c+d, {a, -1}});
dijkstra2(1, 0, i);
dijkstra2(n, 1, i);
g2[b].pop_back();
wynik = min(wynik, odl2[0][n] + odl2[1][1]);
for(int j = 1; j <= n; ++j) odl2[0][j] = odl2[1][j] = 1e18;
}
dijkstra2(1, 0, -1);
dijkstra2(n, 1, -1);
wynik = min(wynik, odl2[0][n] + odl2[1][1]);
if(wynik != 1e18) printf("%lld\n", wynik);
else printf("-1");
return 0;
}
