#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int NN = 2e2+5;
const int MM = 5e4+5;
int w[NN][NN];
int who[NN][NN];
int from[NN];
int treeedge[MM];
bool done[NN];
ll dst[NN];
ll SD[NN], TD[NN]; // distances from the start and end, respectively
ll TMP[NN];
struct edge{
int u, v, w, fost, id; // fost = flipping cost
};
edge E[MM];
int n,m;
ll dij(/*vector<edge> &edges, */ll *d, int S, int T, bool tree) {
memset(w, 0x3f, sizeof w);
bug("yart");
REP(i,m) {
edge e = E[i];
if (w[e.u][e.v] > e.w) {
w[e.u][e.v] = e.w;
who[e.u][e.v] = e.id;
}
}
memset(done, 0, sizeof done);
memset(d, 0x3f, sizeof SD);
d[S] = 0;
while (1) {
int v = -1; ll bad = 0x3f3f3f3f3f3f3f3f;
REP(i,n) {
if (!done[i] && d[i] < bad) {
bad = d[i]; v = i;
}
}
if(v == -1) break;
done[v] = 1;
REP(u, n) {
if (!done[u] && d[u] > d[v] + w[v][u]) {
d[u] = d[v] + w[v][u];
from[u] = v;
}
}
}
if (tree) {
REP(i,n) {
if (done[i] && i != S) {
int f = from[i];
treeedge[who[f][i]] = 1;
bug("Tree!", who[f][i], E[who[f][i]].u, E[who[f][i]].v);
}
}
}
return d[T];
}
ll floy[NN][NN];
signed main(){
IOS();
cin>>n>>m;
memset(floy, 0x3f, sizeof floy);
REP(i,m) {
cin>>E[i].u>>E[i].v>>E[i].w>>E[i].fost; --E[i].u; --E[i].v;
E[i].id = i;
MN(floy[E[i].u][E[i].v], E[i].w);
}
REP(i,n) floy[i][i] = 0;
REP(k,n) REP(i,n) REP(j,n) {
MN(floy[i][j], floy[i][k] + floy[k][j]);
}
ll ftrip = dij(SD, 0, n-1, 1);
ll btrip = dij(TD, n-1, 0, 1);
ll re = ftrip + btrip;
bug(re);
REP(i,m) {
// try flipping this bit
bug(i, treeedge[i]);
if (treeedge[i]) {
// ok, just brute it
swap(E[i].u, E[i].v);
ll go = dij(TMP, 0, n-1, 0);
ll bk = dij(TMP, n-1, 0, 0);
bug(go, bk);
MN(re, go+bk+E[i].fost);
swap(E[i].u, E[i].v);
}else{
int u = E[i].u, v = E[i].v;
ll newf;
if (SD[v] == inf) newf = ftrip;
else newf = SD[v] + floy[u][n-1] + E[i].w;
ll newb;
if (TD[v] == inf) newb = btrip;
else newb = TD[v] + floy[u][0] + E[i].w;
MN(newf, ftrip); MN(newb, btrip);
bug(newf, newb);
MN(re, newf + newb + E[i].fost);
}
}
if (re >= inf-10) re = -1;
cout<<re<<endl;
}
/*
// fear: what if T cannot be reached by v?????
2 2
1 2 7 3
1 2 4 8
*/
