#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5;
const int INF = 1e18;
struct EdgeInfo {
int c, v, p;
};
vector<EdgeInfo> adj[maxn];
vector<pair<int, int>> g[maxn];
int dist[maxn];
bool visited[maxn];
void dijkstra(int total) {
fill(dist, dist + total + 1, INF);
dist[1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, 1});
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (visited[u]) continue;
visited[u] = true;
for (auto [v, w] : g[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!visited[v])
pq.push({dist[v], v});
}
}
}
}
void solve() {
int n, m;
cin >> n >> m;
int total = n;
for (int i = 0; i < m; ++i) {
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u].push_back({c, v, p});
adj[v].push_back({c, u, p});
g[u].push_back({v, p});
g[v].push_back({u, p});
}
for (int u = 1; u <= n; ++u) {
sort(adj[u].begin(), adj[u].end(), [](const EdgeInfo &a, const EdgeInfo &b) {
return a.c < b.c;
});
int l = 0;
for (int r = 1; r < adj[u].size(); ++r) {
if (adj[u][r].c != adj[u][l].c) {
if (r - l == 1) {
g[u].push_back({adj[u][l].v, 0});
} else {
int sum = 0;
for (int k = l; k < r; ++k)
sum += adj[u][k].p;
++total;
g[u].push_back({total, 0});
for (int k = l; k < r; ++k) {
int v = adj[u][k].v;
int p = adj[u][k].p;
g[v].push_back({total, 0});
g[total].push_back({v, sum - p});
}
}
l = r;
}
}
int r = adj[u].size();
if (r - l == 1) {
g[u].push_back({adj[u][l].v, 0});
} else {
int sum = 0;
for (int k = l; k < r; ++k)
sum += adj[u][k].p;
++total;
g[u].push_back({total, 0});
for (int k = l; k < r; ++k) {
int v = adj[u][k].v;
int p = adj[u][k].p;
g[v].push_back({total, 0});
g[total].push_back({v, sum - p});
}
}
}
dijkstra(total);
if (dist[n] < INF / 2) cout << dist[n] << '\n';
else cout << -1 << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
