#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 {
int v, u, c, p;
};
int M = 400'010;
vector<vector<pair<ll, ll>>> g(M);
vector<map<int, int>> suma(M);
vector<Edge> edges;
ll inf = 1e18;
vector<vector<ll>> dijkstra(int s) {
vector<vector<ll>> dist(M, vector<ll>(2, inf));
priority_queue<pair<ll, pair<ll, ll>>> pq;
int 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 = [&](int v, int 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;
int v = eg.u;
if(msk==1) {
suma[v][eg.c] -= eg.p;
}
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);
}
}
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);
int n,m;
cin >> n >> m;
for(int i=0; i<m; ++i) {
int 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(int v=1; v<=n; ++v) {
for(auto[u, i] : g[v]) {
suma[v][edges[i].c] += edges[i].p;
}
}
ll ans = inf;
vector<vector<ll>> dist = dijkstra(1);
int 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;
}
