#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
const ll linf = 1e18;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
vector<map<int, ll>> vc(n);
vector<ar<int, 4>> edges(m + 1);
vector<vector<ar<int, 2>>> g(n);
for (int i = 0; i < m;i++) {
int u, v, c, w;
cin >> u >> v >> c >> w;
--u, --v;
g[u].push_back({v, i});
g[v].push_back({u, i});
vc[u][c] += w;
vc[v][c] += w;
edges[i] = {u, v, c, w};
}
edges[m] = {-1, -1, -1, -1};
priority_queue<ar<ll, 4>, vector<ar<ll, 4>>, greater<ar<ll, 4>> > pq;
vector dp(n, vector (m + 1, vector(2, linf))); // 1 changed, 0 not changed
dp[0][m][1] = 0;
pq.push({0, 0, m, 1});
while (!pq.empty()) {
auto [w, u, ed, t] = pq.top();
pq.pop();
if (w != dp[u][ed][t])
continue;
for (auto [v, ed2] : g[u]) {
int c = edges[ed2][2];
int w2 = edges[ed2][3];
ll cur = vc[u][c] - w2;
if (t == 1 && edges[ed][2] == c)
cur -= edges[ed][3];
if (dp[v][ed2][0] > w + cur)
pq.push({dp[v][ed2][0] = w + cur, v, ed2, 0});
if (dp[v][ed2][1] > w + w2)
pq.push({dp[v][ed2][1] = w + w2, v, ed2, 1});
}
}
ll ans = linf;
for (int i = 0; i <= m;i++)
for (int j = 0; j < 2;j++)
ans = min(ans, dp[n - 1][i][j]);
cout << (ans >= linf ? -1 : ans);
}
int32_t main() {
#ifdef Behruz
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
