#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
ll a,b,c,d,t,n,m,l,q;
ll dst[100007];
bool odw[100007];
vector<pair<ll,pair<ll,ll>>>g[100007];
vector<pair<ll,ll>>g2[1000007];
map<ll,ll>mp[100007],sm[100007];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(ll i=0;i<m;i++){
cin>>a>>b>>c>>d;
a--;
b--;
c--;
g[a].pb({c,{b,d}});
g[b].pb({c,{a,d}});
sm[a][c]+=d;
sm[b][c]+=d;
}
ll ak=0;
for(ll i=0;i<n;i++){
mp[i][-1]=ak++;
for(auto it : sm[i]){
mp[i][(it).ff]=ak++;
}
}
for(ll i=0;i<n;i++){
for(auto j : g[i]){
g2[mp[i][-1]].pb({min(sm[i][j.ff]-j.ss.ss,j.ss.ss),mp[j.ss.ff][-1]});
g2[mp[i][-1]].pb({0,mp[j.ss.ff][j.ff]});
g2[mp[i][j.ff]].pb({sm[i][j.ff]-j.ss.ss,mp[j.ss.ff][-1]});
}
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
pq.push({0,0});
for(ll i=0;i<ak;i++)dst[i]=INFL;
while(pq.size()){
auto pom=pq.top();
pq.pop();
if(odw[pom.ss])continue;
odw[pom.ss]=1;
dst[pom.ss]=pom.ff;
for(pair<ll,ll> i : g2[pom.ss]){
pq.push({i.ff+pom.ff,i.ss});
}
}
if(dst[mp[n-1][-1]]==INFL)dst[mp[n-1][-1]]=-1;
cout<<dst[mp[n-1][-1]];
return 0;
}
