#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(x) x.begin(), x.end()
#define pb push_back
const int MXN = 5e5+5;
int n, m, N, xr[MXN], C[MXN], P[MXN];
vector<int> g[MXN];
vector<pll> G[MXN];
ll dis[MXN];
unordered_map<int, int> V[MXN], cnt[MXN];
unordered_map<int, ll> sum[MXN];
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
for(int i=0,u,v; i<m; i++) {
cin >> u >> v >> C[i] >> P[i];
xr[i] = u^v;
g[u].pb(i);
g[v].pb(i);
}
N = n+1;
for(int v=1; v<=n; v++)
for(int i : g[v]) {
if(!V[v][C[i]])
V[v][C[i]]=N++;
cnt[v][C[i]]++;
sum[v][C[i]] += P[i];
}
for(int v=1; v<=n; v++) {
for(auto [c, u] : V[v])
G[v].pb(pll(u, 0));
for(int i : g[v]) {
G[v].pb(pll(v^xr[i], cnt[v][C[i]]==1?0:P[i]));
G[v].pb(pll(V[v^xr[i]][C[i]], 0));
G[V[v][C[i]]].pb(pll(v^xr[i], sum[v][C[i]]-P[i]));
}
}
priority_queue<pll> pq;
pq.push({0, 1});
fill(dis+2, dis+N, 1e18);
while(!pq.empty()) {
ll d = -pq.top().first;
int v = pq.top().second;
pq.pop();
if(dis[v]!=d) continue;
for(auto [u, w] : G[v])
if(dis[u]>d+w)
pq.push(pll(-(dis[u]=d+w), u));
}
cout << (dis[n]==1e18 ? -1 : dis[n]) << '\n';
return 0;
}
