#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, m, a, b, c, p;
long long d[100000], pre[200000], sum[200000], cur;
bool check[100000];
priority_queue<pair<long long, int>> pq;
vector<array<int, 4>> g[100000];
int main()
{
setup();
cin >> n >> m;
while (m--)
{
cin >> a >> b >> c >> p;
c--;
g[a - 1].push_back({b - 1, c, p});
g[b - 1].push_back({a - 1, c, p});
}
fill_n(d, 100000, 2e18);
d[0] = 0;
pq.push({0, 0});
while (!pq.empty())
{
a = pq.top().second;
pq.pop();
if (check[a])
{
continue;
}
check[a] = true;
for (auto & i : g[a])
{
pre[i[1]] = 2e18;
sum[i[1]] = 0;
}
for (auto & i : g[a])
{
sum[i[1]] += i[2];
}
for (auto & i : g[a])
{
pre[i[1]] = min(pre[i[1]], d[i[0]] + sum[i[1]]);
}
for (auto & i : g[a])
{
cur = min({d[a] + i[2], d[a] + sum[i[1]] - i[2], pre[i[1]] - i[2]});
if (cur < d[i[0]])
{
d[i[0]] = cur;
pq.push({-d[i[0]], i[0]});
}
}
}
cout << (d[n - 1] < 2e18 ? d[n - 1] : -1);
return 0;
}
