#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define el cout<<"\n";
#define fi first
#define se second
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 5;
const ll INF = 1e18;
int n, m, ok2 = 1;
vector<ll> dp(MAXN, INF);
map<int, vector<pair<int, ll>>> g[MAXN];
vector<unordered_map<int, ll>> dp2(MAXN), ts(MAXN);
void AC() {
FOR(i, 1, n) {
for(auto& it : g[i]) {
int c = it.fi;
for(auto& edge : it.se) {
ts[i][c] += edge.se;
}
}
}
priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> mp;
dp[1] = 0;
mp.push({0, {1, 0}});
while(mp.size()) {
pair<ll, pair<int, int>> x = mp.top(); mp.pop();
int u = x.se.fi, c = x.se.se;
ll tmp = x.fi;
if(!c) if(dp[u] != tmp) continue;
if(c) if(dp2[u][c] != tmp) continue;
for(auto y : g[u]) {
//int v = y.fi, cc = y.se.fi, p = y.se.se;
if(!c) {
for(auto& it : g[u]) {
int cc = it.fi;
for(auto& edge : it.se) {
int v = edge.fi;
ll p = edge.se;
if(g[u][cc].size() > 1) {
if(dp[v] > min(tmp + p, tmp + ts[u][cc] - p)) {
dp[v] = min(tmp + p, tmp + ts[u][cc] - p);
mp.push({dp[v], {v, 0}});
}
if(!dp2[v].count(cc) || dp2[v][cc] > tmp) {
dp2[v][cc] = tmp;
mp.push({dp2[v][cc], {v, cc}});
}
} else {
if(dp[v] > tmp) {
dp[v] = tmp;
mp.push({tmp, {v, 0}});
}
}
}
}
}else {
if(g[u].count(c)) {
for(auto& edge : g[u][c]) {
int v = edge.fi;
ll p = edge.se;
if(dp[v] > tmp + ts[u][c] - p) {
dp[v] = tmp + ts[u][c] - p;
mp.push({dp[v], {v, 0}});
}
}
}
}
}
}
if(dp[n] == INF) cout << -1;
else cout << dp[n];
}
main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
FOR(i, 1, m) {
int u, v, c; ll p; cin >> u >> v >> c >> p;
g[u][c].push_back({v, p});
g[v][c].push_back({u, p});
}
AC();
return 0;
}
// T.T<33~~
