#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a), end(a)
#define F first
#define S second
using namespace std;
using ll = long long;
struct Edge {
int to;
int c;
ll p;
};
int const N = 100005;
int n, m;
vector<vector<Edge>> adj;
set<pair<int, int>> bio;
ll cost[2 * N];
struct Item {
ll cur_cost;
int ver;
int par;
bool friend operator>(Item const &lhs, Item const &rhs) {
return lhs.cur_cost > rhs.cur_cost;
}
};
void load() {
cin >> n >> m;
adj.resize(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});
}
}
ll solve() {
priority_queue<Item, vector<Item>, greater<>> pq;
pq.push({0, 0, -1});
while (!pq.empty()) {
auto [cur_cost, ver, par] = pq.top();
if (ver == n - 1) return cur_cost;
pq.pop();
if (bio.count({par, ver})) continue;
bio.emplace(par, ver);
for (auto [u, col, price] : adj[ver]) {
if (par == u) continue;
cost[col] += price;
}
for (auto [u, col, price] : adj[ver]) {
if (!bio.count({-1, u})) {
pq.push({cur_cost + cost[col] - price, u, -1});
}
if (!bio.count({ver, u})) {
pq.push({cur_cost + price, u, ver});
}
}
for (auto [u, col, price] : adj[ver]) {
cost[col] = 0;
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
load();
cout << solve() << '\n';
return 0;
}
