#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const ll N=1e5+5;
map<ll,vector<array<ll,3>>>g[N];
ll dp[N];
map<ll,ll>dp2[N],psum[N];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,m;
cin>>n>>m;
for(ll i=1;i<=m;i++){
ll a,b,c,p;
cin>>a>>b>>c>>p;
g[a][c].pb({b,c,p});
g[b][c].pb({a,c,p});
psum[a][c]+=p;
psum[b][c]+=p;
}
priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>>pq;
const ll inf=(ll)1e18;
fill(dp,dp+N,inf);
pq.push({0,1,0});
dp[1]=0;
while(!pq.empty()){
auto [cost,x,c]=pq.top();
pq.pop();
if(c!=0){
if(dp2[x][c]!=cost) continue;
for(auto [y,col,p]:g[x][c]){
ll case1=psum[x][col]-p;
if(cost+case1<dp[y]){
dp[y]=cost+case1;
pq.push({dp[y],y,0});
}
}
}
else{
if(dp[x]!=cost) continue;
for(auto edges:g[x]){
for(auto [y,col,p]:edges.second){
ll case1=psum[x][col]-p;
if(cost+case1<dp[y]){
dp[y]=cost+case1;
pq.push({dp[y],y,0});
}
ll case2=p;
if(cost+case2<dp[y]){
dp[y]=cost+case2;
pq.push({dp[y],y,0});
}
ll case3=cost;
if(!dp2[y].count(col)||case3<dp2[y][col]){
dp2[y][col]=case3;
pq.push({dp2[y][col],y,col});
}
}
}
}
}
cout<<(dp[n]<inf?dp[n]:-1);
}
