/*
Going for ST1 => full conversion
* first idea: "node" retrievable using boolean number of states, since each road will have two sides. represent a => 0 and b => 1
* this is still NM-ish as every road is checked N times from each place?
*/
#include <bits/stdc++.h>
using namespace std;
void fast() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
long long a = rand();
long long b = rand();
return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define endl '\n'
// #define double long double
#define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;
// #define cerr if(0) cerr
#define debug(x) cerr << #x << ": " << x << endl;
int n, m;
const int MXN = 1005;
const int MXM = 200005;
int a[MXM], b[MXM], colour[MXM], price[MXM];
vector<pair<int, int>> adj[MXN];
int dist[2][MXM][2];
map<int, map<int, int>> adj_count;
map<int, map<int, int>> adj_sum;
signed main() {
ran(); fast();
for (int i=0; i<2; i++) for (int j=0; j<MXM; j++) dist[i][j][0] = dist[i][j][1] = LLONG_MAX / 4;
cin >> n >> m;
for (int i=1; i<=m; i++) {
cin >> a[i] >> b[i] >> colour[i] >> price[i];
adj[a[i]].push_back({i, 1}); // connect it to the other side
adj[b[i]].push_back({i, 0}); // connect it to the other side
adj_count[a[i]][colour[i]]++;
adj_count[b[i]][colour[i]]++;
adj_sum[a[i]][colour[i]]+=price[i];
adj_sum[b[i]][colour[i]]+=price[i];
}
// initially at node 1, previous road '0', was not changed, price is 0
b[0] = 1; // just to setup the initial
min_pq<pair<int, pair<pair<int, int>, int>>> process;
process.push({0, {{1, 0}, 0}}); // node (a or b), prevroad, didwechange
int ans = LLONG_MAX;
while (!process.empty()) {
auto x = process.top(); process.pop();
int di = x.first;
int prevroad = x.second.first.second;
int node = x.second.first.first;
int onode = node;
if (node == 0) {
node = a[prevroad];
}
else {
node = b[prevroad];
}
int waschanged = x.second.second;
if (node == n) {
ans = min(ans, di);
}
// cout << node << ' ' << prevroad << " " << waschanged << ": " << di << endl;
if (dist[onode][prevroad][waschanged] < di) {
continue;
}
dist[onode][prevroad][waschanged] = di;
for (auto x: adj[node]) {
int road = x.first, other = x.second;
// what is the cost of going there?
if (road == prevroad) continue; // don't go back the previous road, why would you?
if (adj_count[node][colour[road]] == 1) {
// then it's free!
if (di < dist[other][road][0]) {
process.push({di, {{other, road}, 0}});
dist[other][road][0] = di;
}
}
else {
// there's a lot of these roads with this colour, so we must change something
int cost_change = price[road]; // what is the cost of changing this road, so we can use it?
int cost_others = adj_sum[node][colour[road]] - cost_change; // what is the cost of changing all the other roads?
if (colour[prevroad] == colour[road]) {
// the old road is one of those other roads
if (waschanged) {
// old road colour already changed, don't change again!
cost_others -= price[prevroad];
}
}
assert(cost_change >= 0);
assert(cost_others >= 0);
// now we consider changing this road:
if (di + cost_change < dist[other][road][1]) {
process.push({di + cost_change, {{other, road}, 1}});
dist[other][road][1] = di + cost_change;
}
// or changing all other roads:
if (di + cost_others < dist[other][road][0]) {
process.push({di + cost_others, {{other, road}, 0}});
dist[other][road][0] = di + cost_others;
}
}
}
}
if (ans == LLONG_MAX) cout << -1 << endl;
else cout << ans << endl;
}
