#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 5e4+5;
const string NAME = "";
struct Edge{
int from,to,weight,cost,pos;
}edge[MAXN];
int n,m,rs=2e9;
int dist1[205],distN[205],distrev1[205],distrevN[205];
Edge trace1[205],traceN[205];
bool vis[MAXN];
vector<Edge> adj[205],rev[205];
vector<int> v;
multiset<int> ms[205][205];
void dijkstra1(int u, int dist[], Edge trace[]){
fill(dist+1,dist+n+1,1e9);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[u]=0, pq.ins(0,u);
while(!pq.empty()){
pair<int,int> top=pq.top();
pq.pop();
if(top.fi>dist[top.se]) continue;
for(Edge& e : adj[top.se]){
if(top.se!=e.from) continue;
if(dist[e.to]>top.fi+e.weight) dist[e.to]=top.fi+e.weight, trace[e.to]=e, pq.ins(dist[e.to],e.to);
}
}
}
void dijkstrarev(int u, int dist[]){
fill(dist+1,dist+n+1,1e9);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[u]=0, pq.ins(0,u);
while(!pq.empty()){
pair<int,int> top=pq.top();
pq.pop();
if(top.fi>dist[top.se]) continue;
for(Edge& e : rev[top.se])
if(dist[e.from]>top.fi+e.weight) dist[e.from]=top.fi+e.weight, pq.ins(dist[e.from],e.from);
}
}
void dijkstra2(int u, int dist[]){
fill(dist,dist+n+1,1e9);
fill(vis,vis+n+1,0);
dist[u]=0;
for(int i = 1; i<=n; ++i){
int u=0;
for(int j = 1; j<=n; ++j)
if(!vis[j]&&dist[j]<dist[u]) u=j;
vis[u]=1;
for(int j = 1; j<=n; ++j)
if(!ms[u][j].empty()) dist[j]=min(dist[j],dist[u]+*ms[u][j].begin());
}
}
int main()
{
tt;
if(fopen((NAME + ".INP").c_str(), "r")) fo;
cin >> n >> m;
for(int i = 1; i<=m; ++i){
cin >> edge[i].from >> edge[i].to >> edge[i].weight >> edge[i].cost, edge[i].pos=i;
adj[edge[i].from].pb(edge[i]), adj[edge[i].to].pb(edge[i]);
rev[edge[i].to].pb(edge[i]);
}
dijkstra1(1,dist1,trace1), dijkstra1(n,distN,traceN);
if(dist1[n]<1e9&&distN[1]<1e9) rs=min(rs,dist1[n]+distN[1]);
if(dist1[n]<1e9){
for(int i = n; i>1; i=trace1[i].from)
vis[trace1[i].pos]=1, v.pb(trace1[i].pos);
}
if(distN[1]<1e9){
for(int i = 1; i<n; i=traceN[i].from)
vis[traceN[i].pos]=1, v.pb(traceN[i].pos);
}
dijkstrarev(1,distrev1), dijkstrarev(n,distrevN);
for(int i = 1; i<=m; ++i)
if(!vis[i]){
int a=dist1[n],b=distN[1];
a=min(a,dist1[edge[i].to]+distrevN[edge[i].from]+edge[i].weight);
b=min(b,distN[edge[i].to]+distrev1[edge[i].from]+edge[i].weight);
if(a<1e9&&b<1e9) rs=min(rs,a+b+edge[i].cost);
}
for(int i = 1; i<=m; ++i)
ms[edge[i].from][edge[i].to].ins(edge[i].weight);
for(int& i : v){
int x=edge[i].from, y=edge[i].to, w=edge[i].weight;
ms[x][y].erase(ms[x][y].find(w));
ms[y][x].ins(w);
dijkstra2(1,dist1), dijkstra2(n,distN);
if(dist1[n]<1e9&&distN[1]<1e9) rs=min(rs,dist1[n]+distN[1]+edge[i].cost);
ms[y][x].erase(ms[y][x].find(w));
ms[x][y].ins(w);
}
if(rs>=2e9) cout << -1;
else cout << rs;
}
