#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define int long long
const ll MOD = 1e9+7;
void add(ll &x, const ll y){
x+= y;
if(x>=MOD) x-= MOD;
}
bool maximize(ll &x, const ll y){
if(x < y){
x = y; return true;
}
return false;
}
bool minimize(ll &x, const ll y){
if(x > y){
x = y; return true;
}
return false;
}
const ll MAX = 2e5+10, INF = 1e18;
ll n,m;
ll dp[MAX];
map<ll,ll>dp2[MAX], costSum[MAX];
struct Edge{
ll from, to, color, cost;
Edge(ll _from=0, ll _to=0, ll _color=0, ll _cost=0){
from = _from;
to = _to;
color = _color;
cost = _cost;
}
};
map<ll,vector<Edge>>adj[MAX];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("shortcut.in","r",stdin);
// freopen("shortcut.out","w",stdout);
cin>>n>>m;
for(int i =1;i<=m;i++){
ll u,v,c,p;
cin>>u>>v>>c>>p;
adj[u][c].pb(Edge(u,v,c,p));
adj[v][c].pb(Edge(v,u,c,p));
costSum[u][c] += p;
costSum[v][c] += p;
}
memset(dp, 0x3f, sizeof dp);
priority_queue<vector<ll>>q;
dp[1] = 0;
q.push({0,1,0});
while(!q.empty()){
ll u = q.top()[1], c = q.top()[2], cost = q.top()[0];
q.pop();
if(c){
if(dp2[u][c] != -cost) continue;
ll case3 = costSum[u][c] - cost;
for(auto e : adj[u][c]){
if(case3 - e.cost < dp[e.to]){
dp[e.to] = case3 - e.cost;
q.push({-dp[e.to], e.to, 0});
}
}
}
else{
if(dp[u] != -cost) continue;
for(auto &j : adj[u]){
for(auto e : j.se){
ll case1 = e.cost - cost;
if(case1 < dp[e.to]){
dp[e.to]= case1;
q.push({-dp[e.to], e.to,0});
}
ll case2 = costSum[u][e.color] - cost - e.cost;
if(case2 < dp[e.to]){
dp[e.to] = case2;
q.push({-dp[e.to], e.to, 0});
}
ll case3 = -cost;
if(!dp2[e.to].count(e.color) || dp2[e.to][e.color] > case3){
dp2[e.to][e.color] = case3;
q.push({-dp2[e.to][e.color], e.to, e.color});
}
}
}
}
}
cout<<(dp[n] >= INF ? -1 : dp[n])<<endl;
}
