#include "bits/stdc++.h"
#pragma optimize ("Bismillahirrahmanirrahim")
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n"
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
//#define m (l+r)/2
constexpr int N=200005;
constexpr int MOD=1000000007;
constexpr int INF2 = LLONG_MAX;
constexpr int INF=(int)1e18;
constexpr int LOG=30;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//to think//
/*
* graph approach
* dp
* dividing the problem to smaller statements
* finding the real constraint
* sqrt decomposition
* greedy approach
* pigeonhole principle
* rewriting the problem/equality
* bitwise approaches
* binary search if monotonic
* divide and conquer
* combinatorics
* inclusion - exclusion
* think like bfs
*/
inline int in()
{
int x;cin >> x;
return x;
}
inline string in2()
{
string x;cin >> x;
return x;
}
void solve()
{
int n=in(),m=in();
map<int,pii> mp[n+2];
vector<array<int,2>> vis(n+2,{0,0});
vector<array<int,3>> v[n+2];
int dist[n+2][2];
dist[1][1]=0;
for(int i=2;i<=n;i++) dist[i][0]=dist[i][1]=INF;
for(int i=1;i<=m;i++)
{
int a=in(),b=in(),c=in(),d=in();
v[a].pb({b,c,d});
v[b].pb({a,c,d});
mp[a][c].ff+=d;
mp[b][c].ff+=d;
mp[b][c].ss++;
mp[a][c].ss++;
}
priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> pq;
pq.push({0,1,INF,INF});
while(!pq.empty())
{
array<int,4> c=pq.top();pq.pop();
map<int,int> mp2;
if(c[2]==INF)
{
if(vis[c[1]][1]) continue;
vis[c[1]][1]=1;
}
else
{
if(vis[c[1]][0]) continue;
vis[c[1]][0]=1;
}
// cout << c[0] << " " << c[1] << " " << c[2] << " " << c[3] << endl;
for(auto x:v[c[1]]) mp2[x[1]]=INF;
for(auto x:v[c[1]])
{
if(vis[x[0]][0] || vis[x[0]][1]) mp2[x[1]]=min({mp2[x[1]],dist[x[0]][0],dist[x[0]][1]});
}
for(auto x:v[c[1]])
{
if(mp[c[1]][x[1]].ss==1)
{
if(c[0]<dist[x[0]][1])
{
dist[x[0]][1]=c[0];
pq.push({c[0],x[0],INF,INF});
}
}
if(c[0]+x[2]<dist[x[0]][0])
{
dist[x[0]][0]=c[0]+x[2];
pq.push({c[0]+x[2],x[0],x[1],x[2]});
}
}
for(auto x:v[c[1]])
{
if(c[0]+mp[c[1]][x[1]].ff-x[2]-(c[2]==x[1] ? c[3] : 0) < dist[x[0]][1])
{
dist[x[0]][1]=c[0]+mp[c[1]][x[1]].ff-x[2];
pq.push({c[0]+mp[c[1]][x[1]].ff-x[2],x[0],INF,INF});
}
}
for(auto x:v[c[1]])
{
if(dist[x[0]][1] > mp2[x[1]] + mp[c[1]][x[1]].ff - x[2])
{
dist[x[0]][1]= mp2[x[1]] + mp[c[1]][x[1]].ff - x[2];
pq.push({dist[x[0]][1],x[0],INF,INF});
}
}
}
cout << ( (dist[n][1]==INF && dist[n][0]==INF) ? -1 : min(dist[n][1],dist[n][0])) << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
cout << fixed << setprecision(15);
int t=1;//cin>> t;
for(int i=1;i<=t;i++)
{
// cout << "Case #" << i << ": ";
solve();
}
return 0;
}
