#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <utility>
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define all(x) begin(x), end(x)
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct edge {
int node, color; ll price;
};
void solve() {
int n, m; cin >> n >> m;
vector<vector<edge>> adj(n);
for (int i = 0; i < m; i++) {
int u, v, c, p; cin >> u >> v >> c >> p; u--; v--;
adj[u].pb({v, c, p});
adj[v].pb({u, c, p});
}
vector<map<int, ll>> prices(n);
for (int i = 0; i < n; i++) {
for (auto x : adj[i]) {
prices[i][x.color] += x.price;
}
}
vector<map<int, ll>> dist(n);
priority_queue<pair<ll, pair<ll, pair<int, int>>>, vector<pair<ll, pair<ll, pair<int, int>>>>, greater<>> pq;
pq.push({0, {0, {0, -1}}});
while (!pq.empty()) {
auto curr = pq.top(); pq.pop();
auto dis = curr.first; auto weight = curr.second.first;
auto node = curr.second.second.first; auto color = curr.second.second.second;
if (dist[node][color] <= dis) {
continue;
}
dist[node][color] = dis;
for (auto x : adj[node]) {
if (!dist[x.node].count(x.color)) {
dist[x.node][x.color] = LLONG_MAX;
}
if (!dist[x.node].count(-1)) {
dist[x.node][-1] = LLONG_MAX;
}
if (dist[x.node][x.color] > dis + x.price) {
pq.push({dis + x.price, {x.price, {x.node, x.color}}});
}
if (color == x.color){
if (dist[x.node][-1] > dis + prices[node][x.color] - x.price - weight) {
pq.push({dis + prices[node][x.color] - x.price - weight, {x.price, {x.node, -1}}});
}
}
else {
if (dist[x.node][-1] > dis + prices[node][x.color] - x.price) {
pq.push({dis + prices[node][x.color] - x.price, {x.price, {x.node, -1}}});
}
}
}
}
if (dist[n - 1].empty()) {
cout << -1; return;
}
ll res = LLONG_MAX;
for (auto x : dist[n - 1]) {
res = min(res, x.second);
}
cout << res;
}
int main() {
FAST_IO;
//freopen("fcolor.in", "r", stdin);
//freopen("fcolor.out", "w", stdout);
//TEST_CASES;
solve(); cout << endl;
/*int a; cin >> a;
for (int i = 1; i <= a; i++){
cout << "Case #" << i << ": ";
solve();
cout << endl;
}*/
}
