#include <bits/stdc++.h>
using namespace std;
int a,b;
struct node{
int x,w,id;
bool operator<(const node &o) const {
if (x != o.x) return x < o.x;
if (w != o.w) return w < o.w;
return id < o.id;
}
};
multiset <node> z[1005];
multiset <node> z1[1005];
bool check[100005];
long long cnt[205][5];
long long bruh=1e16;
pair<int,int> trace[205];
void dijkstra(int sta,int fin,int id){
for (int i=1;i<=a;i++){
cnt[i][id]=bruh;
}
for (int i=1;i<=a;i++){
trace[i]={0,0};
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({0,sta});
cnt[sta][id]=0;
while (q.size()){
pair<int,int> pos=q.top();
q.pop();
int val=pos.first;
int pos1=pos.second;
if (val>cnt[pos1][id]){
continue;
}
if (id<=1){
for (auto [p,w,nxt]:z[pos1]){
if (cnt[p][id]>val+w){
cnt[p][id]=val+w;
trace[p]={pos1,nxt};
q.push({cnt[p][id],p});
}
}
}else{
for (auto [p,w,nxt]:z1[pos1]){
if (cnt[p][id]>val+w){
cnt[p][id]=val+w;
trace[p]={pos1,nxt};
q.push({cnt[p][id],p});
}
}
}
}
if (id<=1){
for (int i=fin;i!=sta && i!=0;i=trace[i].first){
check[trace[i].second]=true;
}
}
}
struct edge{
int x,y,w,d;
};
edge sad[50005];
long long cnt1[205];
long long dijkstra1(int sta,int fin){
for (int i=1;i<=a;i++){
cnt1[i]=bruh;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({0,sta});
cnt1[sta]=0;
while (q.size()){
auto [val,pos]=q.top();
q.pop();
if (val>cnt1[pos]){
continue;
}
for (auto [p,w,id]:z[pos]){
if (cnt1[p]>val+w){
cnt1[p]=val+w;
q.push({cnt1[p],p});
}
}
}
return cnt1[fin];
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
for (int i=1;i<=b;i++){
int x,y,w,d;
cin >> x >> y >> w >> d;
z[x].insert({y,w,i});
z1[y].insert({x,w,i});
sad[i]={x,y,w,d};
}
dijkstra(1,a,0);
dijkstra(a,1,1);
dijkstra(1,a,2);
dijkstra(a,1,3);
long long min1=min(1LL*(cnt[a][0]+cnt[1][1]),bruh);
for (int i=1;i<=b;i++){
auto [u,v,w,d]=sad[i];
if (1LL*(min(cnt[v][0]+w+cnt[u][3],cnt[a][0])+min(cnt[v][1]+cnt[u][2]+w,cnt[1][1]) +d)>min1){
continue;
}
if (check[i]){
auto it=z[u].find({v,w,i});
z[u].erase(it);
z[v].insert({u,w,i});
min1=min(min1,1LL*(dijkstra1(1,a)+dijkstra1(a,1)+d));
it=z[v].find({u,w,i});
z[v].erase(it);
z[u].insert({v,w,i});
}else{
min1=min(min1,1LL*(min(cnt[v][0]+w+cnt[u][3],cnt[a][0])+min(cnt[v][1]+cnt[u][2]+w,cnt[1][1]) +d));
}
}
if (min1==bruh){
cout << -1 << "\n";
return 0;
}
cout << min1 << "\n";
// cout << cnt[3][0]+cnt[5][3]+89 << "\n";
// if (min1==bruh){
// cout << -1 << "\n";
// }else{
// cout << min1 << "\n";
// }
return 0;
}
