#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Edge {
ll v, u, c, p;
};
ll M = 100'010;
vector<vector<pair<ll, ll>>> g(M);
vector<map<ll, ll>> suma(M);
vector<map<ll, vector<pair<ll, ll>>>> best(M);
vector<Edge> edges;
ll inf = 1e18;
vector<vector<ll>> dijkstra(ll s) {
vector<vector<ll>> dist(4*M, vector<ll>(2, inf));
vector<vector<set<int>>> ile(2, vector<set<int>>(M));
priority_queue<pair<ll, pair<ll, ll>>> pq;
ll index = 0;
for(auto e : edges) {
if(e.v==s) {
dist[index][0] = suma[s][e.c]-e.p;
dist[index][1] = e.p;
pq.push({-dist[index][0], {index, 0}});
pq.push({-dist[index][1], {index, 1}});
}
++index;
}
auto check = [&](ll v, ll msk, ll val) {
if(dist[v][msk] > val) {
dist[v][msk] = val;
pq.push({-val, {v,msk}});
}
};
while(pq.size()) {
auto[dv, stat] = pq.top(); pq.pop();
auto[i,msk] = stat;
Edge eg = edges[i];
dv*=-1;
if(dist[i][msk]!=dv) continue;
ll v = eg.u;
if(msk==1) {
suma[v][eg.c] -= eg.p;
}
if(ile[msk][v].size() < 5 && ile[msk][v].find(eg.c)==ile[msk][v].end()) {
for(auto[u,idx] : g[eg.u]) {
if((idx^1)==i) continue;
Edge e = edges[idx];
if(e.c!=eg.c || msk==1) {
check(idx, 1, dv + e.p);
check(idx, 0, dv + suma[v][e.c] - e.p);
} else {
check(idx, 1, dv + e.p);
}
}
ile[msk][v].insert(eg.c);
}
int idx = -1;
for(auto[a,b] : best[v][eg.c]) {
++idx;
if(idx > 5) break;
if((b^1)==i) continue;
Edge e = edges[b];
if(msk==1 && suma[v][e.c] <= 2*e.p) check(b, 0, dv + suma[v][e.c] - e.p);
}
if(msk==1) {
suma[v][eg.c] += eg.p;
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n,m;
cin >> n >> m;
for(ll i=0; i<m; ++i) {
ll a, b, c, p;
cin >> a >> b >> c >> p;
g[a].push_back({b,2*i});
g[b].push_back({a,2*i+1});
edges.push_back({a,b,c,p});
edges.push_back({b,a,c,p});
}
for(ll v=1; v<=n; ++v) {
for(auto[u, i] : g[v]) {
suma[v][edges[i].c] += edges[i].p;
best[v][edges[i].c].push_back({edges[i].p, i});
}
for(auto&[a,b] : best[v]) {
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
}
}
ll ans = inf;
vector<vector<ll>> dist = dijkstra(1);
ll idx=0;
for(auto e : edges) {
if(e.u==n) {
ans = min(ans, dist[idx][0]);
ans = min(ans, dist[idx][1]);
}
++idx;
}
if(ans==inf) cout << "-1\n";
else cout << ans << "\n";
return 0;
}
