//#pragma GCC optimize "Ofast"
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<ll> point;
#define X real()
#define Y imag()
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const ll INF = 1e17;
const ll sqrtn = 440;
const ll modulo = 1e9+7;
const ll siz = 262144;
const ll hashp = 923981238;
const ll hashm = 932439994;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int ll
int reversededge;
struct edge{
int u,v,c,d,idx;
bool Reverse;
edge(){}
edge(int u,int v,int c,int d,int idx,bool R=false):u(u),v(v),c(c),d(d),idx(idx),Reverse(R){}
bool isActive(){
if(Reverse)return reversededge==idx;
else return reversededge!=idx;
}
};
edge edgelist[50001];
vector<edge> adj[201];
int distfrom1[201];
int distfromn[201];
int distto1[201];
int distton[201];
bool visited[201];
int n;
pair<int,int> dijkastra(){
int cost = INF;
int cost2 = INF;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
q.emplace(0,1);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
if(curr.second==n){cost=curr.first;break;}
visited[curr.second]=true;
for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
}
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)visited[i]=false;
q.emplace(0,n);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
if(curr.second==1) {cost2 = curr.first;break;}
visited[curr.second]=true;
for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
}
for(int i=1;i<=n;i++)visited[i]=false;
return {cost,cost2};
}
void solve() {
int m;
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v,c,d;
cin >> u >> v >> c >> d;
edgelist[i] = {u,v,c,d,i};
adj[u].emplace_back(u,v,c,d,i);
adj[v].emplace_back(v,u,c,d,i,true);
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
q.emplace(0,1);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
visited[curr.second]=true;
distfrom1[curr.second]=curr.first;
for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
}
for(int i=1;i<=n;i++)visited[i]=false;
q.emplace(0,n);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
visited[curr.second]=true;
distfromn[curr.second]=curr.first;
for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
}
for(int i=1;i<=n;i++)visited[i]=false;
q.emplace(0,1);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
visited[curr.second]=true;
distto1[curr.second]=curr.first;
for(auto&i:adj[curr.second])if(!i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
}
for(int i=1;i<=n;i++)visited[i]=false;
q.emplace(0,n);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
visited[curr.second]=true;
distton[curr.second]=curr.first;
for(auto&i:adj[curr.second])if(!i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
}
for(int i=1;i<=n;i++)visited[i]=false;
pair<int,int> def = dijkastra();
int ans = def.first+def.second;
for(int i=1;i<=m;i++){
// Check if its useful
if(edgelist[i].d+edgelist[i].c+distfrom1[edgelist[i].v]+distton[edgelist[i].u]<def.first or edgelist[i].d+edgelist[i].c+distfromn[edgelist[i].v]+distto1[edgelist[i].u]<def.second){
reversededge = i;
pair<int,int> inter = dijkastra();
ans = min(ans,inter.first+inter.second+edgelist[i].d);
} else {
reversededge = i;
pair<int,int> inter = dijkastra();
if(ans>inter.first+inter.second+edgelist[i].d){
cout << "L at " << i << '\n';
}
}
}
cout << (ans>=INF ? -1 : ans) << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("mock.txt","r",stdin);
// freopen(".out","w",stdout);
// int t;
// cin >> t;
// while(t--)
solve();
}
