#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 205
#define MAXM 50005
int n,m;
int dist[MAXN][MAXN];
array<int,4> edg[MAXM];
vector<pair<int,int> > adj[MAXN];
int EDGST;
int dijkstra(int st, int rev){
int dis[MAXN];
for(int i=0; i<MAXN; i++) dis[i] = 1e17;
dis[st] = 0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;//w,nd
pq.push({0,st});
while(!pq.empty()){
int wei = pq.top().first, v=pq.top().second; pq.pop();
if(dis[v] != wei) continue;
for(auto ahc : adj[v]){
if(ahc.second==rev) continue;
int nd = ahc.first; int nw = edg[ahc.second][2];
if(wei + nw < dis[nd]){
dis[nd] = wei+nw;
pq.push({dis[nd],nd});
}
}
if(v==EDGST){
int nd = edg[rev][0]; int nw = edg[rev][2];
if(wei + nw < dis[nd]){
dis[nd] = wei+nw;
pq.push({dis[nd],nd});
}
}
}
if(st==n) return dis[1];
else return dis[n];
}
int32_t main(){
for(int i=0; i<MAXN; i++){
for(int j=0; j<MAXN; j++){
if(i==j) dist[i][j]=0;
else dist[i][j]=1e17;
}
}
cin>>n>>m;
for(int i=0; i<m; i++){
int u,v,c,d;
cin>>u>>v>>c>>d;
edg[i] = {u,v,c,d};
adj[u].push_back(make_pair(v,i));
dist[u][v]=min(dist[u][v],c);
}
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 an = dist[1][n] + dist[n][1];
for(int i=0; i<m; i++){
//can lower?
int dis_to = min(dist[1][n], dist[1][edg[i][1]] + edg[i][2] + dist[edg[i][0]][n]);
int dis_fr = min(dist[n][1], dist[n][edg[i][1]] + edg[i][2] + dist[edg[i][0]][1]);
if(dis_to + dis_fr + edg[i][3] < an){
EDGST = edg[i][1];
int dis1 = dijkstra(1,i);
int dis2 = dijkstra(n,i);
//if(i==1) cout<<dis1<<' '<<dis2<<endl;
an = min(an, dis1+dis2+edg[i][3]);
}
}
if(an < 1e15) cout<<an;
else cout<<-1;
}
