#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll inf = 2e18;
struct node
{
int to, c, p;
};
int main()
{
int n, m;
cin >> n >> m;
vector<node> adj[n];
for (int i = 0; i < m; i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
adj[--a].push_back({--b, c, d});
adj[b].push_back({a, c, d});
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<ll> d(n, inf);
d[0] = 0;
pq.push({0, 0});
while (!pq.empty())
{
auto t = pq.top();
ll dd = t.first, cur = t.second;
pq.pop();
if (d[cur] != dd)
continue;
ll mn = inf;
map<ll, ll> cst, f;
for (auto u : adj[cur])
{
int to = u.to, c = u.c, p = u.p;
f[c]++, cst[c] += p;
}
for (auto it : cst)
mn = min(mn, it.second);
for (auto u : adj[cur])
{
int to = u.to, c = u.c, p = u.p;
if (f[c] == 1 && d[to] > d[cur])
d[to] = d[cur], pq.push({d[to], to});
else
{
if (f.size() < m)
{
if (d[to] > d[cur] + p)
d[to] = d[cur] + p, pq.push({d[to], to});
}
else
{
ll v = min(cst[c] - p, mn + p);
if (d[to] > d[cur] + v)
d[to] = d[cur] + v, pq.push({d[to], to});
}
}
}
}
cout << (d[n - 1] == inf ? -1 : d[n - 1]) << '\n';
return 0;
}
