#include <bits/stdc++.h>
using namespace std;
#define kien long long
//#define int long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define pii pair<kien, kien>
#define dembit(a) __builtin_popcountll(a)
#define task "kien"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define debug(x) cout << x << " "
#define down cout << "\n"
const kien MOD = 1e14 + 7;
const int NTEST = 100;
const int Million = 1e6;
const int MXN = 2e5 + 5;
//const double INF = 1e9;
mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
kien rand(kien l, kien r) {
assert(l <= r);
return uniform_int_distribution<kien>(l, r)(rd);
}
kien n, k, m, u, v, h, d[MXN], trace[MXN];
kien maxx, minn, vtr, s, t, r, x, l, timer, add;
struct KBB {
kien mot, hai, ba;
};
vector <KBB> dp[MXN];
void dijkstra (int s) {
priority_queue <pii, vector <pii>, greater <pii>> q;
d[s] = 0;
q.push({d[s], s});
while (!q.empty()) {
auto [du, u] = q.top();
// cout << du << " " << u << "\n";
q.pop();
if (du > d[u]) continue;
map <int, int> pp;
for (auto v : dp[u]) {
pp[v.hai]++;
}
for (auto v : dp[u]) {
if (pp[v.hai] > 1) {
if (d[v.mot] > d[u] + v.ba) {
d[v.mot] = d[u] + v.ba;
q.push({d[v.mot], v.mot});
}
}
else {
// cout << v.mot << "g ";
if (d[v.mot] > d[u]) {
// cout << "z ";
d[v.mot] = d[u];
q.push({d[v.mot], v.mot});
}
}
}
}
if (d[n] == MOD) {
cout << -1;
return;
}
cout << d[n];
}
void solve() {
kien c, p;
cin >> n >> m;
FOR (i, 1, n) d[i] = MOD;
FOR (i, 1, m) {
cin >> u >> v >> c >> p;
dp[u].pb({v, c, p});
dp[v].pb({u, c, p});
}
dijkstra(1);
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(task".inp", "r")) {
fin(task); fou(task);
}
int tt = 1; // cin >> tt;
while(tt--) {
solve();
}
cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}
