#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;
vector<int> topo;
vector<pair<int, pair<int, int>>> g[MAXN];
void SUB1() {
vector<ll> dp(n + 1, INF);
vector<vector<ll>> dp2(n + 1, vector<ll> (m + 1, INF));
vector<vector<int>> dem(n + 1, vector<int>(m + 1, 0));
vector<vector<ll>> ts(n + 1, vector<ll>(m + 1, 0));
FOR(i, 1, n) {
for(auto x : g[i]) {
dem[i][x.se.fi]++;
ts[i][x.se.fi] += x.se.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 == 0 && dp[u] < tmp) continue;
if(c != 0 && dp2[u][c] < tmp) continue;
for(auto y : g[u]) {
int v = y.fi, cc = y.se.fi, p = y.se.se;
if(!c) {
if(dem[u][cc] > 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][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(cc == c) {
if(dp[v] > tmp + ts[u][cc] - p) {
dp[v] = tmp + ts[u][cc] - 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 x, y, c, p; cin >> x >> y >> c >> p;
g[x].push_back({y, {c, p}});
g[y].push_back({x, {c, p}});
}
if(n <= 1000 && m <= 2000) SUB1();
return 0;
}
// T.T<33~~
