#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<map<ll, ll> > costadj(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]++;
costadj[a][c] += p;
costadj[b][c] += p;
}
vector<map<ll, ll> > dp(n);
priority_queue<pair<pii, pii> > q; // dist, cur, prev, color, cost
q.push({{-1, 0}, {-1, -1}});
ll ans = INF;
while (!q.empty()) {
ll d, cur, c, cost;
d=q.top().f.f;
cur = q.top().f.s;
c = q.top().s.f;
cost=q.top().s.s;
q.pop();
if (dp[cur][c] > 0) continue;
dp[cur][c] = -d;
// cout << cur << c << -d << endl;
if (cur == n-1) ans = min(ans, dp[cur][c]);
for (auto val: adj[cur]) {
// move along an edge not with color c
if (val.s.f != c) {
if (cntadj[cur][val.s.f] != 1) q.push({{-(dp[cur][c] + val.s.s), val.f}, {val.s.f, val.s.s}}); // color edge out
else q.push({{-(dp[cur][c]), val.f}, {val.s.f, val.s.s}});
q.push({{-(dp[cur][c] + costadj[cur][val.s.f]), val.f}, {-1, -1}}); // color all in
} else {
if (cntadj[cur][val.s.f] != 2) {
assert(cntadj[cur][val.s.f] != 1);
q.push({{-(dp[cur][c] + val.s.s), val.f}, {val.s.f, val.s.s}}); // color edge out
} else q.push({{-(dp[cur][c]), val.f}, {val.s.f, val.s.s}}); // color edge out
q.push({{-(dp[cur][c] + costadj[cur][val.s.f] - cost), val.f}, {-1, -1}}); // color all in
}
}
}
cout << ((ans >= INF) ? -1 : ans-1) << endl;
}
