#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
using namespace std;
vector<array<int, 3>> adj[100001];
vector<int> D[100001];
int sum[200001];
int sz[100001];
vector<int> id[100001];
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("TEST.in", "r", stdin);
//freopen("TEST.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, c, w;
cin >> u >> v >> c >> w;
adj[u].push_back({v, c, w});
adj[v].push_back({u, c, w});
id[u].push_back((int)adj[v].size() - 1);
id[v].push_back((int)adj[u].size() - 1);
}
for (int i = 1; i <= n; i++)
{
sz[i] = (int)adj[i].size();
D[i].resize(sz[i] + 1);
}
D[1][sz[1]] = 1;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;
q.push({1, 1, sz[1]});
while (!q.empty())
{
auto [d, u, t] = q.top();
int pc, pw;
if (t == sz[u]) tie(pc, pw) = make_pair(-1, 0);
else
{
pc = adj[u][t][1];
pw = adj[u][t][2];
}
q.pop();
for (int i = 0; i < sz[u]; i++) sum[adj[u][i][1]] = 0;
for (int i = 0; i < sz[u]; i++) sum[adj[u][i][1]] += adj[u][i][2];
for (int i = 0; i < sz[u]; i++)
{
const auto& [v, c, w] = adj[u][i];
int s = sum[c];
int k = id[u][i];
if (pc == c) s -= pw;
if (t != sz[u] && v == adj[u][t][0]) continue;
if (D[u][t] + w < D[v][k] || !D[v][k])
{
D[v][k] = D[u][t] + w;
q.push({D[v][k], v, k});
}
if (D[u][t] + s - w < D[v][sz[v]] || !D[v][sz[v]])
{
D[v][sz[v]] = D[u][t] + s - w;
q.push({D[v][sz[v]], v, sz[v]});
}
}
}
int ans = (int)1e18;
for (int i = 0; i <= sz[n]; i++) ans = min(ans, D[n][i]);
if (ans == (int)1e18) cout << -1;
else cout << ans - 1;
return 0;
}
