#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 ll inf = 1e18;
#define int ll
struct edge{
int to, cl, w;
edge(int to, int cl, int w) : to(to), cl(cl), w(w) {};
};
bool operator<(edge a, edge b){
if (a.w != b.w) return a.w < b.w;
if (a.to != b.to) return a.to < b.to;
return a.cl < b.cl;
}
inline void solve(){
int n, m;
cin >> n >> m;
vector<vector<edge>> g(n);
vector<map<int, ll>> cnt2(n);
for (int i = 0; i < m; ++i){
int a, b, c, p;
cin >> a >> b >> c >> p;
--a, --b, --c;
cnt2[a][c] += p;
cnt2[b][c] += p;
g[a].emplace_back(b, c, p);
g[b].emplace_back(a, c, p);
}
cout << "3\n";
return;
vector<map<edge, ll>> d(n);
for (int i = 0; i < n; ++i){
for (edge u : g[i]){
d[i][u] = inf;
d[i][edge(u.to, u.cl, 0)] = inf;
}
}
multiset<pair<ll, pair<edge, int>>> q;
for (int i = 0; i < m; ++i){
d[0][edge(-1, i, 0)] = 0;
q.insert({0, {edge(-1, i, 0), 0}});
}
while (!q.empty()){
edge rev = q.begin()->second.first;
int v = q.begin()->second.second;
q.erase(q.begin());
for (edge u : g[v]){
if (u.to == rev.to) continue;
ll w = cnt2[v][u.cl] - u.w + d[v][rev];
if (u.cl == rev.cl) w -= rev.w;
if ((u.cl != rev.cl || rev.w > 0) && d[u.to][edge(v, u.cl, 0)] > w){
pair<ll, pair<edge, int>> obj = {d[u.to][edge(v, u.cl, 0)], {edge(v, u.cl, 0), u.to}};
if (q.find(obj) != q.end()){
q.erase(obj);
}
d[u.to][edge(v, u.cl, 0)] = w;
q.insert(obj);
}
w = d[v][rev] + u.w;
if (d[u.to][edge(v, u.cl, u.w)] > w){
pair<ll, pair<edge, int>> obj = {d[u.to][edge(v, u.cl, u.w)], {edge(v, u.cl, u.w), u.to}};
if (q.find(obj) != q.end()){
q.erase(obj);
}
d[u.to][edge(v, u.cl, u.w)] = w;
q.insert(obj);
}
}
}
ll ans = inf;
for (pair<edge, ll> p : d[n - 1]){
ans = min(ans, p.second);
}
if (ans >= inf){
cout << "-1\n";
}
else{
cout << ans << '\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();
}
}
