#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll
struct Edge{
int to,cost,price;
Edge(){}
Edge(int tt,int cc,int pp){
to = tt,cost = cc,price = pp;
}
};
const int inf = 1e18;
const int mxn = 1e5+10;
int n,m;
bitset<mxn> del,tree,vis;
vector<int> g[220],rg[220];
int d1[220],d2[220],pid[220],d3[220],d4[220],d5[220],d6[220],d7[220],d8[220];
vector<Edge> edges;
void add_edge(int a,int b,int c,int d){
g[a].push_back(edges.size());
edges.push_back(Edge(b,c,d));
rg[b].push_back(edges.size());
edges.push_back(Edge(a,c,d));
return;
}
void DIJKSTRA(int st,vector<int> paths[],int dist[]){
fill(dist,dist+220,inf);
memset(pid,-1,sizeof(pid));
vis.reset();
dist[st] = 0;
int now = st;
for(int i = 0;i<n-1;i++){
vis[now] = true;
for(auto eid:paths[now]){
int nxt = edges[eid].to;
if(del[eid])continue;
if(dist[nxt]>dist[now]+edges[eid].cost){
dist[nxt] = dist[now]+edges[eid].cost;
pid[nxt] = eid;
}
}
pii tmp = {inf,-1};
for(int j = 1;j<=n;j++){
if(vis[j])continue;
tmp = min(tmp,make_pair(dist[j],j));
}
if(tmp.sc == -1)break;
now = tmp.sc;
}
return;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i = 0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
add_edge(a,b,c,d);
}
DIJKSTRA(1,g,d1);
for(int i = 1;i<=n;i++){
if(pid[i] != -1)tree[pid[i]>>1] = true;
}
DIJKSTRA(n,g,d2);
for(int i = 1;i<=n;i++){
if(pid[i] != -1)tree[pid[i]>>1] = true;
}
DIJKSTRA(1,rg,d3);
DIJKSTRA(n,rg,d4);
ll ans = inf;
ans = min(ans,d1[n]+d2[1]);
/*
cout<<"d1:";for(int i = 1;i<=n;i++)cout<<d1[i]<<' ';cout<<endl;
cout<<"d2:";for(int i = 1;i<=n;i++)cout<<d2[i]<<' ';cout<<endl;
cout<<"d3:";for(int i = 1;i<=n;i++)cout<<d3[i]<<' ';cout<<endl;
cout<<"d4:";for(int i = 1;i<=n;i++)cout<<d4[i]<<' ';cout<<endl;
*/
for(int i = 0;i<edges.size();i+=2){
if(tree[i>>1]){
del[i] = del[i^1] = true;
add_edge(edges[i].to,edges[i^1].to,edges[i].cost,edges[i].price);
DIJKSTRA(1,g,d5);
DIJKSTRA(n,g,d6);
g[edges[i].to].pop_back();
rg[edges[i^1].to].pop_back();
edges.pop_back();edges.pop_back();
del[i] = del[i^1] = false;
ans = min(ans,d5[n]+d6[1]+edges[i].price);
//cout<<i<<":"<<edges[i^1].to<<' '<<edges[i].to<<":"<<d5[n]<<' '<<d6[1]<<' '<<edges[i].price<<endl;
}
else{
int tans = min(d1[edges[i].to]+d4[edges[i^1].to]+edges[i].cost,d1[n]);
tans += min(d2[edges[i].to]+d3[edges[i^1].to]+edges[i].cost,d2[1]);
tans += edges[i].price;
ans = min(ans,tans);
}
}
cout<<(ans>=inf?-1:ans);
}
