#include "bits/stdc++.h"
#pragma optimize ("Bismillahirrahmanirrahim")
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n"
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
//#define m (l+r)/2
constexpr int N=200005;
constexpr int MOD=1000000007;
constexpr int INF2 = LLONG_MAX;
constexpr int INF=(int)1e15;
constexpr int LOG=30;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//to think//
/*
* graph approach
* dp
* dividing the problem to smaller statements
* finding the real constraint
* sqrt decomposition
* greedy approach
* pigeonhole principle
* rewriting the problem/equality
* bitwise approaches
* binary search if monotonic
* divide and conquer
* combinatorics
* inclusion - exclusion
* think like bfs
*/
inline int in()
{
int x;cin >> x;
return x;
}
inline string in2()
{
string x;cin >> x;
return x;
}
/*
1- sp route cikar (n^2 dijkstra ile)
2- sp routetaki her edge için tekrardan dijkstra(n^2) at
3- sp routetaki edge değilse dist[1][b] + c + d dist[a][n] dene
*/
int n,m;
multiset<array<int,4>> git;
vector<array<int,4>> edge;
multiset<array<int,3>> v[205];
int dijk(int rt)
{
int di[n+2];
bool vis[n+2];
for(int i=1;i<=n;i++) {di[i]=INF;vis[i]=0;}
di[rt]=0;
for(int i=1;i<=n;i++)
{
pii cur={INF,INF};
for(int j=1;j<=n;j++) if(vis[j]==0) cur=min(cur,{di[j],j});
if(cur.ff==INF) break;
vis[cur.ss]=1;
for(array<int,3> x:v[cur.ss]) if(cur.ff+x[1]<di[x[0]]) di[x[0]]=cur.ff+x[1];
}
if(rt==1) return di[n];
else return di[1];
}
void rout(int rt)
{
int di[n+1];
bool vis[n+1];
for(int i=1;i<=n;i++) {di[i]=INF;vis[i]=0;}
di[rt]=0;
array<int,3> par[n+1];
for(int i=1;i<=n;i++)
{
pii cur={INF,INF};
for(int j=1;j<=n;j++) if(vis[j]==0) cur=min(cur,{di[j],j});
if(cur.ff==INF) break;
vis[cur.ss]=1;
for(array<int,3> x:v[cur.ss])
if(cur.ff+x[1]<di[x[0]])
{par[x[0]]={cur.ss,x[1],x[2]};di[x[0]]=cur.ff+x[1];}
}
if(rt==1)
{
if(vis[n]==0) return;
int xd=n;
while(xd!=1)
{
git.insert({par[xd][0],xd,par[xd][1],par[xd][2]});
xd=par[xd][0];
}
}
else
{
int xd=1;
if(vis[1]==0) return;
while(xd!=n)
{
git.insert({par[xd][0],xd,par[xd][1],par[xd][2]});
xd=par[xd][0];
}
}
}
int dist[202][202];
void solve()
{
n=in(),m=in();
for(int i=1;i<=201;i++) for(int j=1;j<=201;j++) dist[i][j]=INF;
for(int i=1;i<=201;i++) dist[i][i]=0;
for(int i=1;i<=m;i++)
{
int a=in(),b=in(),c=in(),d=in();
edge.pb({a,b,c,d});
dist[a][b]=min(dist[a][b],c);
v[a].insert({b,c,d});
}
rout(1);
rout(n);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
int ans=dist[1][n]+dist[n][1];
for(array<int,4> x:edge)
{
int gitme=INF;
int gelme=INF;
if(git.count(x)==1)
{
v[x[0]].erase(v[x[0]].find({x[1],x[2],x[3]}));
v[x[1]].insert({x[0],x[2],x[3]});
gitme=min(gitme,dijk(1));
gelme=min(gelme,dijk(n));
v[x[1]].erase(v[x[1]].find({x[0],x[2],x[3]}));
v[x[0]].insert({x[1],x[2],x[3]});
ans=min(ans,gitme+gelme+x[3]);
}
else
{
gitme=min(gitme,dist[1][n]);
gitme=min(gitme,dist[1][x[1]]+dist[x[0]][n]+x[2]);
gelme=min(gelme,dist[n][1]);
gelme=min(gelme,dist[n][x[1]]+x[2]+dist[x[0]][1]);
ans=min(ans,gitme+gelme+x[3]);
}
}
cout << (ans>=INF ? -1 :ans) << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
cout << fixed << setprecision(15);
int t=1;//t=in();
for(int i=1;i<=t;i++)
{
//cout << "Case #" << i << ": ";
solve();
}
return 0;
}
