#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
constexpr int inf = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<vector<tuple<int,int,int>>> f(n + 1);
for (int i = 0; i < m; ++i) {
int a, b, c, d; cin >> a >> b >> c >> d;
f[a].emplace_back(c,b,d);
f[b].emplace_back(c,a,d);
}
vector<vector<pii>> g(n + 1);
for (int i = 1; i <= n; ++i) {
map<int, int> app;
for (auto [c, node, d] : f[i]) {
app[c]++;
}
for (auto [c, node, d] : f[i]) {
if (app[c] == 1) g[i].emplace_back(node,0);
else g[i].emplace_back(node,d);
}
}
priority_queue<pii,vector<pii>,greater<>> pq;
pq.emplace(0,1);
vector<int> d(n + 1,inf);
vector<bool> visited(n + 1);
while (!pq.empty()) {
auto [cost, cur] = pq.top();pq.pop();
if (visited[cur]) continue;
d[cur] = cost;
visited[cur] = true;
for (auto [child, len] : g[cur]) {
if (visited[child]) continue;
pq.emplace(len + cost,child);
}
}
cout << d[n];
return 0;
}
