#include<bits/stdc++.h>
using ll=long long;
const int N=1e6+5;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define F(i,a,b,c) for(int i=a;i<=b;i+=c)
#define fo(i,a,b,c) for(int i=a;i>=b;i-=c)
#define pb push_back
const int MOD=1e9+7;
#define el cout<<'\n'
#define all(x) x.begin(),x.end()
#define name "robot1"
using namespace std;
ll n,m;
struct tri
{
ll a,b,c,p;
} edge[N];
vector<pll> g[N];
map<pll,ll> mp;
struct ba
{
ll fi,se,th;
};
vector<ba> f[N];
void init()
{
cin>>n>>m;
F(i,1,m,1)
{
ll a,b,c,p;cin>>a>>b>>c>>p;
edge[i]={a,b,c,p};
mp[{a,c}]+=p;
mp[{b,c}]+=p;
f[a].pb({b,c,p});
f[b].pb({a,c,p});
}
}
ll dp[N];
void process()
{
priority_queue<pll,vector<pll>,greater<pll>> h;
F(u,1,n,1)
{
for(auto [v,c,p]:f[u])
{
ll cost=min(1LL*p,mp[{u,c}]-p);
g[u].pb({v,cost});
}
}
F(i,2,n,1) dp[i]=LLONG_MAX;
h.push({dp[1]=0,1});
while(h.size())
{
auto [d,u]=h.top();h.pop();
if(d>dp[u]) continue;
for(auto [v,w]:g[u])
if(dp[v]>d+w)
h.push({dp[v]=d+w,v});
}
cout<<(dp[n]==LLONG_MAX?-1:dp[n]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if(fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
//input:
init();
clock_t begin = clock();
//code:
process();
clock_t end = clock();
cerr<<endl<<"Time run: "<<(float)(end-begin)/CLOCKS_PER_SEC<<" s"<<endl;
return 0;
}
