#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5 + 10; const int M = 2e5 + 10; const ll INF = 1e16; int n, m; int C[M], P[M]; struct edge { int to, i; }; struct state { int v, st, ix, color; }; bool operator < (state x, state y) { return (x.v < y.v); } vector<edge> g[N]; vector<int> order; bool us[N]; pair<ll, int> dp[N][2][2]; map<ll, ll> S[N]; int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n >> m; for(int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back({v, i}); g[v].push_back({u, i}); cin >> C[i] >> P[i]; } for(int i = 1; i <= n; i++) { for(auto [to, x] : g[i]) { S[i][C[x]] += P[x]; } } set<pair<ll, state>> St; for(int i = 1; i <= n; i++) { dp[i][0][0] = dp[i][0][1] = {(i < n ? INF : 0), -1}, dp[i][1][0] = dp[i][1][1] = {(i < n ? INF : 0), -1}; for(int j = 0; j <= 1; j++) { for(int k = 0; k <= 1; k++) { St.insert({dp[i][j][k].first, {i, j, k, -1}}); } } } bool processed[n + 1] = {}; while(!St.empty()) { state t = (St.begin())->second; int cur = t.v, st = t.st, ix = t.ix, color = t.color; ll curdp = dp[cur][st][ix].first; St.erase(St.begin()); processed[cur] = 1; for(auto [to, i] : g[cur]) { if(processed[to]) continue; for(int next_st = 0; next_st <= 1; next_st++) { St.erase({dp[to][next_st][0].first, {to, next_st, dp[to][next_st][0].second}}); St.erase({dp[to][next_st][1].first, {to, next_st, dp[to][next_st][1].second}}); ll newdp = INF, cl = C[i]; if(next_st) newdp = curdp + (S[to][cl] - P[i]); else newdp = curdp + P[i] * (cl != color || !st); if(dp[to][next_st][0].second == cl) dp[to][next_st][0].first = min(dp[to][next_st][0].first, newdp); if(dp[to][next_st][1].second == cl) dp[to][next_st][1].first = min(dp[to][next_st][1].first, newdp); if(dp[to][next_st][0].first > dp[to][next_st][1].first) swap(dp[to][next_st][0], dp[to][next_st][1]); if(newdp < dp[to][next_st][0].first) swap(dp[to][next_st][0], dp[to][next_st][1]), dp[to][next_st][0] = {newdp, cl}; else if(newdp < dp[to][next_st][1].first) dp[to][next_st][1] = {newdp, cl}; St.insert({dp[to][next_st][0].first, {to, next_st, 0, dp[to][next_st][0].second}}); St.insert({dp[to][next_st][1].first, {to, next_st, 1, dp[to][next_st][0].second}}); } } } ll res = min(dp[1][0][0].first, dp[1][1][0].first); cout << (res == INF ? -1 : res); } // for(int cur : order) { // if(cur == n) { // continue; // } // dp[cur][0][0] = dp[cur][0][1] = {INF, -1}; // dp[cur][1][0] = dp[cur][1][1] = {INF, -1}; // vector<pair<int, int>> pr; // for(auto [to, i] : g[cur]) // if(tin[to] < tin[cur]) pr.push_back({to, i}); // map<int, int> S; // map<int, ll> ans[2]; // for(auto [to, i] : g[cur]) { // S[C[i]] += P[i]; // } // for(auto [next, i] : pr) { // for(int st = 0; st <= 1; st++) { // ans[st][C[i]] = INF; // for(int next_st = 0; next_st <= 1; next_st++) { // ans[st][C[i]] = min(ans[st][C[i]], dp[next][next_st][0].first + (st ? S[C[i]] - P[i] : P[i])); // } // } // ans[0][C[i]] = min(ans[0][C[i]], dp[next][1][0].first + (dp[next][1][0].second != C[i]) * P[i]); // ans[0][C[i]] = min(ans[0][C[i]], dp[next][1][1].first + (dp[next][1][1].second != C[i]) * P[i]); // } // for(int st = 0; st <= 1; st++) { // dp[cur][st][0] = {(--ans[st].end())->second, (--ans[st].end())->first}; // if((int)ans[st].size() > 1) { // dp[cur][st][1] = {(--(--ans[st].end()))->second, (--(--ans[st].end()))->first}; // } // } // } // ll res = INF; // for(int st = 0; st <= 1; st++) // res = min(dp[1][st][0].first, res); // cout << (res == INF ? -1 : res);