#include <bits/stdc++.h>
using namespace std;
#define kien long long
//#define int long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define pii pair<kien, kien>
#define dembit(a) __builtin_popcountll(a)
#define task "kien"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define debug(x) cout << x << " "
#define down cout << "\n"
const kien MOD = 1e15 + 7;
const int NTEST = 100;
const int Million = 1e6;
const int MXN = 2e5 + 5;
mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
kien rand(kien l, kien r) {
assert(l <= r);
return uniform_int_distribution<kien>(l, r)(rd);
}
kien n, k, m, u, v, h, d[MXN];
kien maxx, minn, vtr, s, t, r, x, l;
map <int, kien> pp[MXN];
map <int, kien> d2[MXN];
map <int, vector <pii>> dpc[MXN];
struct KBB {
kien mot, hai, ba;
};
struct day {
kien mot, hai, ba;
bool operator < (const day& x) const {
return mot > x.mot;
}
};
vector <KBB> dp[MXN];
void dijkstra (int s) {
priority_queue <day> q;
d[s] = 0;
q.push({d[s], s, 0});
while (!q.empty()) {
auto [du, u, pre] = q.top();
q.pop();
if (du > d[u] and pre == 0) continue;
if (!d2[u].count(pre) || du > d2[u][pre]) continue;
if (pre == 0)
for (auto v : dp[u]) {
if (d[v.mot] > d[u] + (pp[u][v.hai] - v.ba)) {
d[v.mot] = d[u] + (pp[u][v.hai] - v.ba);
q.push({d[v.mot], v.mot, 0});
}
if (d[v.mot] > d[u] + v.ba) {
d[v.mot] = d[u] + v.ba;
q.push({d[v.mot], v.mot, 0});
}
if (!d2[v.mot].count(v.hai) or d2[v.mot][v.hai] > d[u]) {
d2[v.mot][v.hai] = d[u];
q.push({d2[v.mot][v.hai], v.mot, v.hai});
}
}
else {
for (auto v : dpc[u][pre]) {
if (d[v.first] > d2[u][pre] + pp[u][pre] - v.second) {
d[v.first] = d2[u][pre] + pp[u][pre] - v.second;
q.push({d[v.first], v.first, 0});
}
}
}
}
if (d[n] == MOD) {
cout << -1;
return;
}
cout << d[n];
}
void solve() {
kien c, p;
cin >> n >> m;
FOR (i, 1, n) d[i] = MOD;
FOR (i, 1, m) {
cin >> u >> v >> c >> p;
dp[u].pb({v, c, p});
dp[v].pb({u, c, p});
dpc[u][c].pb({v, p});
dpc[v][c].pb({u, p});
pp[u][c] += p;
pp[v][c] += p;
}
dijkstra(1);
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(task".inp", "r")) {
fin(task); fou(task);
}
int tt = 1; // cin >> tt;
while(tt--) {
solve();
}
cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}
