#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iiii tuple<int, int,int,int>
#define ld long double
#define lol pair<pll,pll>
#define iii tuple<int,int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int n,m;
vector<vector<iii>> al(205), tal(205);
vector<tuple<int,int,int,int>> ed;
tuple<vector<int>,vector<int>, vector<int>> dijk(int s, int skip, vector<vector<iii>> & aa){
vector<int> pdist(n+1, 1e15), dist(n+1, 1e15), from(n+1, -1), ways(n+1, 0);
pdist[s]=0;
ways[s]=1;
for(int i=0;i<n;i++){
pll mn=mp((int)1e16,0);
for(int i=1;i<=n;i++){
mn=min(mn, mp(pdist[i], i));
}
//printf("relaxing %lld, %lld\n", mn.f, mn.s);
if (dist[mn.s] < pdist[mn.s]) continue;
dist[mn.s]=pdist[mn.s];
//for(int j=1;j<=n;j++){cout<<dist[j]<<" ";} cout<<endl;
pdist[mn.s]=1e15;
int d=dist[mn.s], c=mn.s;
for(auto [to,w,ind]:aa[c]){
if(dist[to]<d+w or pdist[to]<d+w or ind==skip)continue;
if(dist[to] > d+w and pdist[to] > d+w){
assert(dist[to] == 1e15);
pdist[to]=d+w;
from[to]=ind;
}
}
}
vector<int> ord(n);
iota(all(ord), 1);
stable_sort(all(ord), [&](int a, int b){return dist[a] < dist[b];});
for(auto ind : ord){
for (auto [to, w, ei] : aa[ind]){
if (dist[to] == dist[ind] + w){
ways[to] += ways[ind];
}
}
}
return make_tuple(dist, from, ways);
}
signed main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c,d;cin>>a>>b>>c>>d;
ed.pb({a,b,c,d});
al[a].pb({b,c,i});
tal[b].pb({a,c,i});
}
//auto [at, _a, _aw] = dijk(1, m, tal);
/*for(int i=1;i<=n;i++){
printf("dist from 1 of i %lld is %lld\n", i, at[i]);
}
return 0;*/
vector<vector<int>> anw(m+1), bnw(m+1);
auto [an, af, aw] = dijk(1, m, al);
auto [at, _a, _aw] = dijk(1, m, tal);
auto [bn, bf, bw] = dijk(n, m, al);
auto [bt, _b, _bw] = dijk(n, m, tal);
vector<bool> ona(m+1, 0), onb(m+1, 0);
/*for(int i=1;i<=n;i++){
printf("dist from 1 of i %lld is %lld, ways %lld, from %lld\n", i, at[i],aw[i], af[i]);
printf("dist from n of i %lld is %lld, ways %lld, from %lld\n", i, bt[i],bw[i], bf[i]);
}*/
int cnt=0;
int ce=af[n];
while(ce != -1){
//if(cnt++ > 5)return 0;
//printf("an, path ce %lld\n", ce);
ona[ce]=true;
anw[ce]=get<0>(dijk(1, ce, al));
bnw[ce]=get<0>(dijk(n, ce, al));
ce = af[get<0>(ed[ce])];
}
ce=bf[1];
while(ce != -1){
onb[ce]=true;
anw[ce]=get<0>(dijk(1, ce, al));
bnw[ce]=get<0>(dijk(n, ce, al));
ce = bf[get<0>(ed[ce])];
}
int ans=an[n] + bn[1];
for(int i=0;i<m;i++){
auto [a,b,c,d]=ed[i]; // a --> b now b-->a
int ab, ba;
// use on forward trip
int onbv=(onb[i] ? bnw[i][1] : bn[1]), elsev=(bw[b]-(bn[a]+c == bn[b]? bw[a]:0) >= 1 ? bn[b]+c+at[a] : (int)1e15);
ab=(aw[b] - (an[a]+c == an[b] ? aw[a] : 0) >= 1 ? an[b] + c + d + bt[a] : (int)1e15), ba=min(onbv, elsev);
ans=min(ans,ab+ba);
//printf("reverse %lld to %lld (i %lld), forward ab %lld, ba %lld, onbv %lld, elsev %lld\n", a,b,i,ab,ba, onbv, elsev);
// use on backwards trip
int cond=bw[b] - (bn[a]+c == bn[b] ? bw[a] : 0);
//printf("cond is %lld, bn[b] %lld, at[a] %lld\n", cond, bn[b], at[a]);
ba=(bw[b] - (bn[a]+c == bn[b] ? bw[a] : 0) >= 1 ? bn[b] + c + d + at[a]: (int)1e15);
ab =min((ona[i] ? anw[i][n] : an[n]), (aw[b]-(an[a]+c == an[b]? aw[a]:0) >= 1 ? an[b]+c+bt[a] : (int)1e15));
//printf("reverse %lld to %lld (i %lld), backward ab %lld, ba %lld\n", a,b,i,ab,ba);
ans=min(ans, ba+ab);
}
cout<<(ans > 1e14? -1 : ans);
}
