#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
map<int, vector<tuple<int, int, int>>> edg[100001];
unordered_map<int, ll> sum[100001], dp2[100001];
ll dp[100001];
int n, m;
void solve() {
priority_queue<tuple<ll, int, int>> pq;
pq.push({0, 1, 0});
while (pq.size() > 0) {
ll dist;
int place, color;
tie(dist, place, color) = pq.top();
dist *= -1;
pq.pop();
if (color) {
if (dist != dp2[place][color]) continue;
for (auto edge : edg[place][color]) {
ll newCost = dist + sum[place][color] - get<2>(edge);
if (newCost < dp[get<0>(edge)]) {
dp[get<0>(edge)] = newCost;
pq.push({-dp[get<0>(edge)], get<0>(edge), 0});
}
}
}
else {
if (dist != dp[place]) continue;
for (int i = 0; i < edg[place].size(); i++) {
for (auto edge : edg[place][i]) {
ll newCost = dist + min((ll) get<2>(edge), sum[place][get<1>(edge)] - (ll) get<2>(edge));
if (newCost < dp[get<0>(edge)]) {
dp[get<0>(edge)] = newCost;
pq.push({-dp[get<0>(edge)], get<0>(edge), 0});
}
if (!dp2[get<0>(edge)].count(get<1>(edge)) || dist < dp2[get<0>(edge)][get<1>(edge)]) {
dp2[get<0>(edge)][get<1>(edge)] = dist;
pq.push({-dp2[get<0>(edge)][get<1>(edge)], get<0>(edge), get<1>(edge)});
}
}
}
}
}
cout << ((dp[n] == 1e18) ? -1 : dp[n]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 2; i <= n; i++) dp[i] = 1e18;
for (int i = 0; i < m; i++) {
int from, to, color, cost;
cin >> from >> to >> color >> cost;
edg[from][color].push_back({to, color, cost});
edg[to][color].push_back({from, color, cost});
sum[from][color] += cost;
sum[to][color] += cost;
}
solve();
}
