// barkolorious - 08 December 2024
// in god, do we trust?
#include <bits/stdc++.h>
using namespace std;
#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define all(v) (v).begin(), (v).end()
#define int long long
#define pb push_back
#define sz size
#define fr first
#define sc second
#define __ << " " <<
const int N = 1e5 + 1;
struct Edge {
int to, color, price;
};
map<int, vector<Edge>> adj[N];
int dp[N];
map<int, int> dp2[N], price_sum[N];
void solve () {
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, c, p; cin >> u >> v >> c >> p;
adj[u][c].pb({v, c, p});
adj[v][c].pb({u, c, p});
price_sum[u][c] += p;
price_sum[v][c] += p;
}
fill(dp, dp + N, 1e15);
priority_queue<tuple<int, int, int>> pq; // dist, node, last color
pq.push({0, 1, 0});
dp[1] = 0;
while (!pq.empty()) {
int node, dist, color;
tie(dist, node, color) = pq.top();
pq.pop();
dist = -dist;
if (color) {
if (dp2[node][color] != dist) continue;
for (Edge edge : adj[node][color]) {
int case1 = dist + (price_sum[node][color] - edge.price);
if (case1 < dp[edge.to]) {
dp[edge.to] = case1;
pq.push({-dp[edge.to], edge.to, 0});
}
}
} else {
if (dp[node] != dist) continue;
for (auto colored_edges : adj[node]) {
for (auto edge : colored_edges.sc) {
int case1 = dist + (price_sum[node][edge.color] - edge.price);
if (case1 < dp[edge.to]) {
dp[edge.to] = case1;
pq.push({-dp[edge.to], edge.to, 0});
}
int case2 = dist + edge.price;
if (case2 < dp[edge.to]) {
dp[edge.to] = case2;
pq.push({-dp[edge.to], edge.to, 0});
}
int case3 = dist;
if (!dp2[edge.to].count(edge.color) || case3 < dp2[edge.to][edge.color]) {
dp2[edge.to][edge.color] = case3;
pq.push({-dp2[edge.to][edge.color], edge.to, edge.color});
}
}
}
}
}
cout << ((dp[n] == 1e15) ? -1 : dp[n]) << endl;
}
/*
-- Sample 1 --
Input:
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
Output:
3
-- Sample 2 --
Input:
5 2
1 4 1 2
3 5 1 4
Output:
-1
-- Sample 3 --
Input:
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
Output:
1
-- Sample 4 --
Input:
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
Output:
7
*/
/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\Olympiads\JOI21\JOI21_ho_t4.cpp" -o _run
*/
int32_t main () {
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#endif
#ifdef LOCAL
clock_t __START__ = clock();
FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
#endif
solve();
#ifdef LOCAL
fclose(__FILE_IN__);
fclose(__FILE_OUT__);
cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
#endif
return 0;
}
