#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;
const int MXn = 100005;
const long long oo = 1e18;
const int MOD = 1e9 + 7;
int n, m;
vector<pair<int, long long>> adj[5 * MXn];
vector<tuple<int, int, long long>> huh[MXn];
long long tot[5 * MXn];
long long d[5 * MXn];
void Dijkstra(void) {
fill(d + 1, d + 1 + n + 500000, oo);
d[1] = 0;
using T = pair<long long, int>;
priority_queue<T, vector<T>, greater<>> pq;
pq.emplace(0, 1);
while (sz(pq)) {
int u = pq.top().se, di = pq.top().fi;
pq.pop();
if (d[u] != di) continue;
for (auto [v, w]: adj[u]) if (d[v] > d[u] + w) pq.emplace(d[v] = d[u] + w, v);
}
}
int num;
map<int, int> mp[MXn];
int mapping(int u, int c) {
if (!mp[u].count(c)) mp[u][c] = ++num;
return mp[u][c];
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
num = n;
for (int i = 1, a, b, c, p; i <= m; i++) {
cin >> a >> b >> c >> p;
adj[a].emplace_back(b, p);
adj[b].emplace_back(a, p);
adj[a].emplace_back(mapping(a, c), 0);
adj[b].emplace_back(mapping(b, c), 0);
adj[a].emplace_back(mapping(b, c), 0);
adj[b].emplace_back(mapping(a, c), 0);
adj[mapping(b, c)].emplace_back(a, -p);
adj[mapping(a, c)].emplace_back(b, -p);
tot[mapping(a, c)] += p;
tot[mapping(b, c)] += p;
}
for (int i = n + 1; i <= num; i++) {
for (auto &[v, c]: adj[i]) {
c += tot[i];
}
}
Dijkstra();
cout << (d[n] == oo ? -1 : d[n]);
return 0;
}
