#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 INF = 1E15;
i64 ncost;
#define ONLINE_JUDGE
void solve() {
int n, m;
cin >> n >> m;
vector <i64> dp1(n +1, INF);
map <int, i64> sum[n +1], dp2[n +1];
vector <tuple <int, int, int>> adj[n +1];
for(int i = 1; i <= m; i++) {
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u].emplace_back(v, c, p);
adj[v].emplace_back(u, c, p);
sum[u][c] += p;
sum[v][c] += p;
}
using T = tuple <i64, int, int>;
priority_queue <T, vector <T>, greater <T>> pq; // [cost, ok, node]
pq.emplace(dp1[1] = 0, -1, 1);
while(!pq.empty()) {
auto [cost, ok, node] = pq.top();
pq.pop();
if(ok == -1) {
if(cost != dp1[node]) {
continue;
}
for(auto [child, color, add] : adj[node]) {
// Case 1: Flip neighbours
// Case 2: Flip yourself but don't your child's neighbours
ncost = cost + min(i64(add), sum[node][color] - add);
if(ncost < dp1[child]) {
//cerr << node << " " << cost << " -> " << child << " " << ncost << "\n";
pq.emplace(dp1[child] = ncost, -1, child);
}
// Case 3: Flip yourself and your child's neighbours
if(dp2[child].count(color) == 0 || cost < dp2[child][color]) {
//cerr << "go: " << node << " " << child << " :: " << color << " :: " << cost << "\n";
pq.emplace(dp2[child][color] = cost, color, child);
}
}
} else {
if(cost != dp2[node][ok]) {
continue;
}
// Only Case 1: Flip neighbours (including before)
for(auto [child, color, add] : adj[node]) {
if(color == ok) {
ncost = cost + (sum[node][color] - add);
if(ncost < dp1[child]) {
//cerr << "ex: " << node << " " << ok << " " << cost << " -> " << child << " " << ncost << "\n";
pq.emplace(dp1[child] = ncost, -1, child);
}
}
}
}
}
cout << (dp1[n] == INF ? -1 : dp1[n]);
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
