#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+10;
struct edge{
int v,c; ll p;
};
vector<int> res[MAXN];
map<int,ll> sum[MAXN],dp2[MAXN];
map<int,vector<edge>> adj[MAXN];
ll dp[MAXN];
const ll INF = 1e18;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N,M; cin >> N >> M;
for(int i = 0;i<M;++i){
int a,b,c; ll p; cin >> a >> b >> c >> p;
adj[a][c].push_back({b,c,p});
sum[a][c] += p;
adj[b][c].push_back({a,c,p});
sum[b][c] += p;
}
memset(dp,0x3f,sizeof(dp));
dp[1] = 0; priority_queue<tuple<ll,int,int>> pq; pq.push({0,1,0});
while(!pq.empty()){
ll cd; int u,c; tie(cd,u,c) = pq.top(); pq.pop();
if(c){
if(dp2[u][c] != -cd) continue;
for(auto x : adj[u][c]){
ll nd = sum[u][c]-x.p-cd;
if(dp[x.v] > nd){
dp[x.v] = nd;
pq.push({-nd,x.v,0});
}
}
}
else{
if(dp[u] != -cd) continue;
for(auto col : adj[u]){
for(auto x : col.second){
ll one = sum[u][x.c]-x.p-cd;
if(one < dp[x.v]){
dp[x.v] = one;
pq.push({-one,x.v,0});
}
ll two = x.p-cd;
if(two < dp[x.v]){
dp[x.v] = two;
pq.push({-two,x.v,0});
}
ll three = -cd;
if(!dp2[x.v].count(x.c) || three < dp2[x.v][x.c]){
dp2[x.v][x.c] = three;
pq.push({-three,x.v,x.c});
}
}
}
}
}
if(dp[N] > INF){
cout << -1 << "\n";
}
else{
cout << dp[N] << "\n";
}
return 0;
}
