#include <bits/stdc++.h>
using namespace std;
//#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=100007;
vector<pair<int,pair<int,ll>>>G[N];
ll d[N];
map<int,ll>sum[N];
bool odw[N];
map<int,ll>D[N];
map<int,ll>was[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,a,b,c;
ll x;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>a>>b>>c>>x;
G[a].pb({b,{c,x}});
G[b].pb({a,{c,x}});
sum[a][c]+=x;
sum[b][c]+=x;
}
priority_queue<pair<ll,pair<int,int>>>Q;
d[1]=inf;
for(int i=2;i<=n;i++) d[i]=infl;
Q.push({-inf,{1,0}});
while(!Q.empty())
{
int v=Q.top().nd.st;
int x=Q.top().nd.nd;
int t=-Q.top().st;
//cout<<v<<" "<<x<<" "<<t<<endl;
Q.pop();
if(x==0)
{
if(odw[v]) continue;
odw[v]=1;
for(auto u:G[v])
{
ll X=min(u.nd.nd,sum[v][u.nd.st]-u.nd.nd);
if(t+X<d[u.st])
{
d[u.st]=t+X;
Q.push({-(t+X),{u.st,0}});
}
X=u.nd.nd;
if(D[u.st][u.nd.st]==0||t<D[u.st][u.nd.st])
{
D[u.st][u.nd.st]=t;
Q.push({-(t),{u.st,u.nd.st}});
}
}
}
if(x>0)
{
if(was[v][x]) continue;
was[v][x]=1;
for(auto u:G[v])
{
if(u.nd.st!=x) continue;
ll X=sum[v][u.nd.st]-u.nd.nd;
if(t+X<d[u.st])
{
d[u.st]=t+X;
Q.push({-(t+X),{u.st,0}});
}
}
}
}
if(d[n]==infl) cout<<-1;
else cout<<d[n]-inf;
return 0;
}
