#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int MAX_M = 200005;
int n, m, a[2 * MAX_M], b[2 * MAX_M], c[2 * MAX_M];
ll p[2 * MAX_M];
vector<vector<int>> g;
ll solve() {
priority_queue<tuple<ll, int, bool>> pq;
ll dp[2 * m][2];
for (int i = 0; i < 2 * m; i++) {
dp[i][0] = dp[i][1] = -INF;
}
dp[m - 1][0] = 0;
pq.push({0, m - 1, 0});
while (not pq.empty()) {
auto [d, e_prev, changed] = pq.top();
pq.pop();
if (dp[e_prev][changed] != d) continue;
int u = b[e_prev];
// cout << "! " << d << ' ' << e_prev << ' ' << u << '\n';
map<int, ll> cost;
if (changed) cost[c[e_prev]] -= p[e_prev];
for (int e_nxt : g[u]) {
cost[c[e_nxt]] += p[e_nxt];
}
for (int e_nxt : g[u]) {
ll incur = min(0ll, cost[c[e_nxt]] - p[e_nxt]);
if (d + incur > dp[e_nxt][0]) {
dp[e_nxt][0] = d + incur;
pq.push({dp[e_nxt][0], e_nxt, 0});
}
incur = p[e_nxt];
if (d + incur > dp[e_nxt][1]) {
dp[e_nxt][1] = d + incur;
pq.push({dp[e_nxt][1], e_nxt, 1});
}
}
}
ll ans = -INF;
for (int i = 0; i < 2 * m; i++) {
if (b[i] == n - 1) {
// cout << -dp[i][0] << ' ' << -dp[i][1] << '\n';
ans = max(ans, max(dp[i][0], dp[i][1]));
}
}
return (ans != -INF ? -ans : -1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
m++;
g.resize(n);
for (int i = 0; i < m - 1; i++) {
cin >> a[i] >> b[i] >> c[i] >> p[i];
a[i]--, b[i]--;
p[i] *= -1;
a[i + m] = b[i];
b[i + m] = a[i];
c[i + m] = c[i];
p[i + m] = p[i];
g[a[i]].push_back(i);
g[b[i]].push_back(i + m);
}
cout << solve() << '\n';
return 0;
}
