#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e17 + 10ll;
int main() {
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, pii> > > adj(n);
vector<map<ll, ll> > cntadj(n);
vector<set<ll> > cntin(n);
vector<ll> dist(n, INF);
for (ll i = 0; i < m; i++) {
ll a, b, c, p;
cin >> a >> b >> c >> p;
a--;b--;
adj[a].pb({b, {c, p}});
adj[b].pb({a, {c, p}});
cntadj[a][c]++;
cntadj[b][c]++;
}
priority_queue<pair<ll, pii> > q; // dist, node, edge color
q.push({0, {0, -1}});
vector<int> todo;
int prev = 0;
while (!q.empty() || !todo.empty()) {
if (q.empty() || prev < -q.top().f) {
for (auto cur: todo) {
for (auto val: adj[cur]) {
ll v = val.f;
ll c = val.s.f;
ll p = val.s.s;
if (dist[cur] <= dist[v]) {
if (cntadj[cur][c] == 1ll) {
q.push({-(dist[cur]), {v, -1}});
} else if (cntadj[cur][c] == 2ll && cntin[cur].find(c) != cntin[cur].end()) {
q.push({-(dist[cur]), {v, -1}});
} else if (dist[cur] + p <= dist[v]) {
q.push({-(dist[cur] + p), {v, c}});
}
}
}
}
todo.erase(todo.begin(), todo.end());
}
if (q.empty()) break;
ll cur = q.top().s.f;
ll d = -q.top().f;
ll cur_col = q.top().s.s;
q.pop();
if (d >= dist[cur]) continue;
assert(dist[cur]==INF);
if (cur_col != -1) cntin[cur].insert(cur_col);
dist[cur]=d;
while (!q.empty() && q.top().s.f == cur && -q.top().f == dist[cur]) {
cur = q.top().s.f;
d = -q.top().f;
cur_col = q.top().s.s;
q.pop();
if (cur_col != -1) cntin[cur].insert(cur_col);
}
todo.push_back(cur);
prev = dist[cur];
}
if (dist[n-1] >= INF) dist[n-1] = -1;
cout << dist[n-1] << endl;
}
