#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <ctime>
#include <queue>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll MOD = 1e9 + 7, MX2 = 1e6, SZ = 1e6 + 100, INF = 1e9 * 1e9 + 100;
ll n, m;
struct edge {
ll to, c, p, ind;
};
vector<vector<edge>> gr;
set<tuple<ll, ll, ll>> dists; // dist, v, col
map<pair<ll, ll>, ll> sv;
map<pair<ll, ll>, ll> cnt;
vector<map<ll, vector<ll>>> cols;
signed main() {
fastInp;
cin >> n >> m;
gr.resize(n);
cols.resize(n);
dists.insert({ 0, 0, 0 });
for (int i = 1; i < n; i++) dists.insert({ INF, i, 0 });
for (int i = 0; i < m; i++) {
ll u, v, c, p;
cin >> u >> v >> c >> p;
u--; v--;
gr[u].push_back({ v, c, p, gr[v].size() });
gr[v].push_back({ u, c, p, gr[u].size() - 1 });
cols[u][c].push_back(gr[u].size() - 1);
cols[v][c].push_back(gr[v].size() - 1);
dists.insert({ INF, u, c });
dists.insert({ INF, v, c });
cnt[{v, c}] += p;
cnt[{u, c}] += p;
}
for (auto c : dists) sv[{get<1>(c), get<2>(c)}] = get<0>(c);
ll ds = INF;
while (!dists.empty()) {
tuple<ll, ll, ll> cur = (*dists.begin());
dists.erase(dists.begin());
ll d = get<0>(cur);
ll v = get<1>(cur);
ll c = get<2>(cur);
if (v == n - 1 && c == 0) {
ds = d;
break;
}
if (c == 0) {
for (auto e : gr[v]) {
if (sv[{e.to, 0}] > d + e.p) {
dists.erase({ sv[{e.to, 0}], e.to, 0 });
sv[{e.to, 0}] = d + e.p;
dists.insert({ sv[{e.to, 0}], e.to, 0 });
}
if (sv[{e.to, 0}] > d + cnt[{v, e.c}] - e.p) {
dists.erase({ sv[{e.to, 0}], e.to, 0 });
sv[{e.to, 0}] = d + cnt[{v, e.c}] - e.p;
dists.insert({ sv[{e.to, 0}], e.to, 0 });
}
}
for (auto e : gr[v]) {
if (sv[{e.to, e.c}] > d) {
dists.erase({ sv[{e.to, e.c}], e.to, e.c });
sv[{e.to, e.c}] = d;
dists.insert({ sv[{e.to, e.c}], e.to, e.c });
}
}
}
else {
for (auto ind : cols[v][c]) {
edge e = gr[v][ind];
if (sv[{e.to, 0}] > d + cnt[{v, e.c}] - e.p) {
dists.erase({ sv[{e.to, 0}], e.to, 0 });
sv[{e.to, 0}] = d + cnt[{v, e.c}] - e.p;
dists.insert({ sv[{e.to, 0}], e.to, 0 });
}
}
}
}
ll a = ds;
if (a == INF) {
cout << "-1";
}
else {
cout << a;
}
return 0;
}
/*
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
5 2
1 4 1 2
3 5 1 4
5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20
*/
