#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
using ll = long long;
using db = long double; // or double, if TL is tight
#define int ll
// pairs
#define mp make_pair
#define f first
#define s second
// vectors
#define sz(v) (int)((v).size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
map<int, map<int, vector<pair<int, int>>>> adj;
map<pair<int, int>, int> in;
for (int i = 0; i < m; i++) {
int u, v, c, w; cin >> u >> v >> c >> w;
adj[u][c].emplace_back(v, w);
adj[v][c].emplace_back(u, w);
in[{u, c}] += w; in[{v, c}] += w;
}
using T = tuple<int, int, int>;
map<int, int> dp;
map<pair<int, int>, int> dis;
priority_queue<T, vector<T>, greater<T>> pq;
pq.emplace(0, 1, 0); dis[{1, 0}] = 0;
while (!pq.empty()) {
auto [d, u, c] = pq.top(); pq.pop();
if (c != 0) {
if (dis.count({u, c}) && dis[{u, c}] != d)
continue;
for (auto &[v, w]: adj[u][c]) {
int cost = in[{u, c}] - w;
if (!dp.count(v) || dp[v] > d + cost) {
dp[v] = d + cost;
pq.emplace(dp[v], v, 0);
}
}
} else {
if (dp.count(u) && dp[u] != d) continue;
for (auto &[c2, lAdj]: adj[u]) {
for (auto &[v, w]: lAdj) {
if (!dp.count(v) || dp[v] > in[{u, c2}] - w + d) {
dp[v] = in[{u, c2}] - w + d;
pq.emplace(dp[v], v, 0);
}
if (!dp.count(v) || dp[v] > d + w) {
dp[v] = d + w;
pq.emplace(dp[v], v, 0);
}
if (!dis.count({v, c2}) || dis[{v, c2}] > d) {
dis[{v, c2}] = d;
pq.emplace(dis[{v, c2}], v, c2);
}
}
}
}
}
cout << (dp.count(n) ? dp[n] : -1) << "\n";
}
