// IamHereForFun //
#include <bits/stdc++.h>
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int L = 12;
const int LG = 25;
const int P = 37;
const long long INF = 1e18 + 5;
const int MOD = 1e9 + 7;
const int nx[] = {0, -1, 0, 1}, ny[] = {-1, 0, 1, 0};
int n, m;
vector<array<int, 3>> adj[N];
long long dp[N], col[M], sum[M];
bool vis[N];
void solve()
{
cin >> n >> m;
for (int x = 0; x < m; x++)
{
int a, b, c, p;
cin >> a >> b >> c >> p;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
}
for (int x = 1; x <= n; x++)
{
dp[x] = INF;
vis[x] = 0;
}
priority_queue<pair<long long, int>> pq;
pq.push({0, 1});
dp[1] = 0;
while (!pq.empty())
{
int i = pq.top().second;
pq.pop();
if (vis[i])
continue;
vis[i] = true;
for (array<int, 3> &a : adj[i])
{
sum[a[1]] = 0;
col[a[1]] = INF;
}
for (array<int, 3> &a : adj[i])
{
sum[a[1]] += a[2];
col[a[1]] = min(col[a[1]], dp[a[0]]);
}
for (array<int, 3> &a : adj[i])
{
long long val = min({dp[i] + a[2], dp[i] + sum[a[1]] - a[2], sum[a[1]] + col[a[1]] - a[2]});
int j = a[0];
if (val < dp[j])
{
dp[j] = val;
pq.push({-dp[j], j});
}
}
}
if (dp[n] == INF)
cout << -1;
else
cout << dp[n];
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for (int x = 1; x <= t; x++)
{
solve();
}
return 0;
}
