#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
using arr = array<long long, 3>;
const int N = 1e5 + 5;
map<int, long long> ps[N];
map<int, long long> dp[N];
vector<array<int, 3>> g[N];
map<int, vector<pair<int, int>>> mp[N];//v, c
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, c, w;
cin >> u >> v >> c >> w;
ps[v][c] += w;
ps[u][c] += w;
mp[v][c].emplace_back(u, w);
mp[u][c].emplace_back(v, w);
g[u].push_back({v, w, c});
g[v].push_back({u, w, c});
}
priority_queue<arr, vector<arr>, greater<arr>> pq;
dp[1][0] = 0;
pq.push({0, 0, 1});
while (!pq.empty()) {
auto [cost, color, v] = pq.top();
pq.pop();
//deb(v) deb(color) deb(cost) cout << '\n';
if (dp[v][color] < cost) {
continue;
}
if (v == n && !color) {
cout << cost << '\n';
return 0;
}
if (color) {
for (auto [u, w] : mp[v][color]) {
long long pay = cost;
pay += ps[v][color] - w;
if (!dp[u].count(0) || dp[u][0] > pay) {
dp[u][0] = pay;
pq.push({pay, 0, u});
}
}
} else {
for (auto [u, w, c] : g[v]) {
long long pay = cost;
if (!dp[u].count(c) || dp[u][c] > pay) {
dp[u][c] = pay;
pq.push({pay, c, u});
}
pay += min((long long) w, ps[v][c] - w);
if (!dp[u].count(0) || dp[u][0] > pay) {
dp[u][0] = pay;
pq.push({pay, 0, u});
}
}
}
}
cout << -1 << '\n';
return 0;
}
