#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define int long long
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define sp <<' '<<
#define fi first
#define se second
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
#define all(x) x.begin(),x.end()
#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define DEBUG(x) cout<<#x sp x<<endl;
#define carp(a,b) ((a%MOD)*(b%MOD))%MOD
#define topla(a,b) ((a%MOD)+(b%MOD))%MOD
#define mid (l+r)/2
const int MAXN=205;
const int MAXK=25;
const int MOD=1e9+7;
const int INF=1e18;
int n,m;
vi u,v,c,dd;
deque<pii> adj[MAXN], revadj[MAXN];
bool vis[MAXN];
int d[MAXN];
bool f;
int ans;
void dij(bool b){
//cur. node yok
priority_queue<pii> pq;
FORE(i,1,n+1) {d[i]=INF;vis[i]=false;}
d[1]=0;
pq.push({0,1});
while(!pq.empty()){
auto ell=pq.top();
pq.pop();
int nd=ell.se;
if(vis[nd]) continue;
vis[nd]=true;
if(b){
for(auto el:adj[nd]){
int kom=el.fi;
int cost=el.se;
if(d[kom]>d[nd]+cost){
d[kom]=d[nd]+cost;
pq.push({-d[kom],kom});
}
}
}
else{
for(auto el:revadj[nd]){
int kom=el.fi;
int cost=el.se;
if(d[kom]>d[nd]+cost){
d[kom]=d[nd]+cost;
pq.push({-d[kom],kom});
}
}
}
}
if(d[n]==INF) f=false;
else ans+=d[n];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("out.txt","w",stdout);
cin>>n>>m;
u.resize(m);
v.resize(m);
c.resize(m);
dd.resize(m);
FOR(i,m){
cin>>u[i]>>v[i]>>c[i]>>dd[i];
adj[u[i]].pb({v[i],c[i]});
revadj[v[i]].pb({u[i],c[i]});
}
int res=INF;
FOR(i,m){
//i.yi invertle
f=true;
ans=0;
adj[v[i]].pb({u[i],c[i]});
adj[u[i]].pop_front();
dij(1); //adj de 1'den n'e
adj[v[i]].pop_back();
adj[u[i]].pb({v[i],c[i]});
revadj[u[i]].pb({v[i],c[i]});
revadj[v[i]].pop_front();
dij(0); //revadj de 1'den n'e
revadj[u[i]].pop_back();
revadj[v[i]].pb({u[i],c[i]});
if(f) res=min(res,dd[i]+ans);
}
f=true;
ans=0;
dij(1);dij(0);
if(f) res=min(res,ans);
if(res==INF) cout<<-1<<endl;
else cout<<res<<endl;
}
