#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iii pair<ll,pair<int,int>>
#define fi first
#define se second
struct duongdi
{
int to,c;
ll p;
};
const int maxn=1e5+7;
const ll maxx=1e18+7;
map<int,ll>psum[maxn];
map<int,ll>dp2[maxn];
map<int,vector<duongdi>>graph[maxn];
ll dp[maxn];
int n,m;
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,c,w;
cin>>x>>y>>c>>w;
graph[x][c].push_back({y,c,w});
graph[y][c].push_back({x,c,w});
psum[x][c]+=w;
psum[y][c]+=w;
}
for(int i=1;i<=n;i++){
dp[i]=maxx;
}
priority_queue<iii,vector<iii>,greater<iii>>q;
dp[1]=0;
q.push(make_pair(0,make_pair(1,0)));
while(q.size()){
int u=q.top().se.fi;
int du=q.top().fi;
int c=q.top().se.se;
q.pop();
// cout<<u<<" "<<du<<" "<<c<<"\n";
if(c){
if(dp2[u][c]!=du)continue;
for(auto p:graph[u][c]){
ll case1=psum[u][c]-p.p;
if(case1+du<dp[p.to]){
dp[p.to]=case1+du;
q.push(make_pair(case1+du,make_pair(p.to,0)));
}
}
}
else{
if(du!=dp[u])continue;
for(auto &cc:graph[u]){
for(auto p:cc.second){
ll case1=psum[u][p.c]-p.p;
if(dp[p.to]>case1+du){
dp[p.to]=case1+du;
q.push(make_pair(case1+du,make_pair(p.to,0)));
}
ll case2=p.p;
if(dp[p.to]>case2+du){
dp[p.to]=case2+du;
q.push(make_pair(case2+du,make_pair(p.to,0)));
}
ll case3=du;
if(!dp2[p.to].count(p.c)||dp2[p.to][p.c]>case3){
dp2[p.to][p.c]=case3;
q.push(make_pair(case3,make_pair(p.to,p.c)));
}
}
}
}
}
// for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
// cout<<"\n";
cout<<((dp[n]==maxx)?-1:dp[n]);
return 0;
}
