//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 50010;
int dis[222][222];
int dist[222];
bool vis[222];
int n,m,big;
struct EDGE{
int u,v,c,d;
} e[maxn];
vector <int> redge[222],edge[222];
pq <pii,vector<pii>,greater<pii> > q;
int ans = 2e9;
bool used[maxn];
vector <int> usededge;
int dijkstra(int st,int ed,int rev) {
memset(dist,inf,sizeof(dist));
dist[st] = 0;
while (!q.empty()) q.pop();
q.push({0,st});
while (!q.empty()) {
pii cur = q.top();
q.pop();
if (dist[cur.se]!=cur.fi) continue;
int u = cur.se;
if (u==ed) return cur.fi;
for (int i:edge[u]) {
int v=e[i].v;
if (i==rev) {
if (e[i].u==u) continue;
else v = e[i].u;
}
if (dist[v] > dist[u] + e[i].c) {
dist[v] = dist[u] + e[i].c;
q.push({dist[v],v});
}
}
}
return big;
}
bool dfs(int st,int ed,int u) {
vis[u]=true;
if (u==ed) return true;
for (int i:edge[u]) {
int v=e[i].v;
if (!vis[v] and dis[st][u] + e[i].c + dis[v][ed]==dis[st][ed] and dfs(st,ed,v)) {
usededge.pb(i);
used[i]=true;
return true;
}
}
return false;
}
void solve(int id) {
//0: n->1 used the inverted edge
//find the shortest path
int st = 1, ed = n;
if (id==1) swap(st,ed);
if (dis[st][ed]==big) return;
int cur = st;
rep(i,1,n+1) vis[i]=false;
dfs(st,ed,cur);
rep(i,0,m) {
if (dis[ed][e[i].v] + dis[e[i].u][st] >= dis[ed][st]) continue;
int tmp;
if (used[i]) {
edge[e[i].v].pb(i);
tmp = dijkstra(st,ed,i);
edge[e[i].v].pop_back();
}
else tmp = dis[st][ed];
if (tmp==big) continue;
ans = min(ans,dis[ed][e[i].v] + e[i].d + e[i].c + dis[e[i].u][st] + tmp);
}
while (!usededge.empty()) used[usededge.back()] = false,usededge.pop_back();
}
int main() {
// freopen("input.txt","r",stdin);
std::ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>m;
memset(dis,inf,sizeof(dis));
big = dis[0][0];
rep(i,1,n+1) dis[i][i] =0 ;
rep(i,0,m) {
cin>>e[i].u>>e[i].v>>e[i].c>>e[i].d;
dis[e[i].u][e[i].v] = min(dis[e[i].u][e[i].v],e[i].c);
redge[e[i].v].pb(i);
edge[e[i].u].pb(i);
}
rep(k,1,n+1)
rep(i,1,n+1)
rep(j,1,n+1) dis[i][j] = min(dis[i][k] + dis[k][j],dis[i][j]);
// debug(ans);
solve(0);
solve(1);
// debug(ans);
ans = min(ans,dis[1][n]+dis[n][1]);
rep(i,0,m) {
if (dis[1][e[i].v] + dis[e[i].u][n] >= dis[1][n]) continue;
if (dis[n][e[i].v] + dis[e[i].u][1] >= dis[n][1]) continue;
ans = min(ans,dis[1][e[i].v] + e[i].c*2 + dis[e[i].u][n] + dis[n][e[i].v] + dis[e[i].u][1] + e[i].d);
}
if (ans==2e9) cout<<-1;
else cout<<ans;
return 0;
}
