#include <bits/stdc++.h>
#define d1(x) cout << #x << " : " << x << endl << flush
#define d2(x, y) cout << #x << " : " << x << " " << #y << " : " << y << endl << flush
#define d3(x, y, z) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << endl << flush
#define d4(x, y, z, a) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << " "<< #a << " : " << a << endl << flush
#define arr(x) array <ll, x>
#define ld long double
#define ll long long
#define int long long
#define pb push_back
#define endl '\n'
#define lc v << 1
#define rc v << 1 | 1
using namespace std;
const int INF = 1e12 + (35 / 10); // 35 ---> 36
const int MAXN = 2e5 + (35 / 10); // 35 ---> 36
map <int, vector<arr(3)>> adj[MAXN];
map <int, int> sm[MAXN], pd[MAXN];
int dp[MAXN];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v, c, p;
cin >> u >> v >> c >> p;
u--;
v--;
adj[u][c].pb({v, c, p});
adj[v][c].pb({u, c, p});
sm[u][c] += p;
sm[v][c] += p;
pd[u][c] = pd[v][c] = INF;
}
for(int i = 1; i < n; i++)
pd[i][0] = dp[i] = INF;
set <arr(3)> s; // dis, u, c
s.insert({0, 0, 0});
dp[0] = pd[0][0] = 0;
while(!s.empty()){
auto [w, u, cool] = *s.begin();
s.erase(s.begin());
if(cool == 0){
if(dp[u] != w)
continue;
for(auto &E : adj[u]){
for(auto [v, c, p] : E.second){
// tt bokon
int eli = w + p;
if(dp[v] > eli){
dp[v] = eli;
s.insert({eli, v, 0});
}
// bagie
eli = sm[u][c] - p + w;
if(dp[v] > eli){
dp[v] = eli;
s.insert({eli, v, 0});
}
/////////////
eli = w;
if(!pd[v].count(c) || pd[v][c] > eli){
pd[v][c] = eli;
s.insert({eli, v, c});
}
}
}
}
else{
if(w != pd[u][cool])
continue;
for(auto [v, c, p] : adj[u][cool]){
int eli = sm[u][c] - p + w;
if(dp[v] > eli){
dp[v] = eli;
s.insert({dp[v], v, 0});
}
}
}
}
if(dp[n - 1] == INF)
dp[n - 1] = -1;
cout << dp[n - 1] << endl;
}
// Ey To Bahane! :_)))
// -------------<3------------- //
/*
Magasan dor shirini:
1. MAXN
2. Input style
3. index or value? Masale In Ast!
4. MOD
*/
