#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define len(v) (int)((v).size())
const int inf = 1e9;
const int sz = 1 << 20;
int tree[sz];
void init(int v, int l, int r){
tree[v] = 0;
if (r - l == 1) return;
int m = (l + r) / 2;
init(v * 2, l, m);
init(v * 2 + 1, m, r);
}
void upd(int v, int l, int r, int qi){
tree[v] += 1;
if (r - l == 1){
return;
}
int m = (l + r) / 2;
if (qi < m) upd(v * 2, l, m, qi);
else upd(v * 2 + 1, m, r, qi);
}
int sum(int v, int l, int r, int ql, int qr){
if (l >= qr || ql >= r) return 0;
if (l >= ql && r <= qr) return tree[v];
int m = (l + r) / 2;
int r1 = sum(v * 2, l, m, ql, qr);
int r2 = sum(v * 2 + 1, m, r, ql, qr);
return r1 + r2;
}
struct event{
int to, cl, w;
event(int to, int cl, int w) : to(to), cl(cl), w(w) {};
};
inline void solve(){
int n, m;
cin >> n >> m;
vector<vector<event>> g(n);
vector<map<int, int>> cnt(n);
for (int i = 0; i < m; ++i){
int a, b, c, p;
cin >> a >> b >> c >> p;
--a, --b, --c;
cnt[a][c]++;
cnt[b][c]++;
g[a].emplace_back(b, c, p);
g[b].emplace_back(a, c, p);
}
vector<ll> d(n, 1e18);
d[0] = 0;
set<pair<int, int>> q;
q.insert({0, 0});
while (!q.empty()){
int v = q.begin()->second;
q.erase(q.begin());
for (event u : g[v]){
int w = 0;
if (cnt[v][u.cl] > 1){
w = u.w;
}
if (d[u.to] > d[v] + w){
if (q.find({d[u.to], u.to}) != q.end()){
q.erase({d[u.to], u.to});
}
d[u.to] = d[v] + w;
q.insert({d[u.to], u.to});
}
}
}
if (d[n - 1] >= inf){
cout << "-1\n";
}
else{
cout << d[n - 1] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout.precision(60);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
