#include <bits/stdc++.h>
using namespace std;
struct E
{
int v, c, w;
E(){}
E(int _v, int _c, int _w)
{
v = _v;
c = _c;
w = _w;
}
};
const int N = 100000 + 5;
const int M = 200000 + 5;
const long long INF = 1e18;
vector<E> g[N];
long long d[N];
long long sum[M];
long long best[M];
int n, m;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, c, w;
cin >> u >> v >> c >> w;
g[u].push_back(E(v, c, w));
g[v].push_back(E(u, c, w));
}
for (int i = 1; i <= n; i++)
d[i] = INF;
for (int i = 1; i <= m; i++)
best[i] = INF;
d[1] = 0;
priority_queue<
pair<long long,int>,
vector<pair<long long,int>>,
greater<pair<long long,int>>
> pq;
pq.push({0, 1});
while (!pq.empty())
{
long long du = pq.top().first;
int u = pq.top().second;
pq.pop();
if (du != d[u])
continue;
for (auto &e : g[u])
{
sum[e.c] += e.w;
if (best[e.c] > d[e.v])
best[e.c] = d[e.v];
}
for (auto &e : g[u])
{
int v = e.v;
int c = e.c;
int w = e.w;
long long t1 = w < sum[c] - w ? w : sum[c] - w;
long long nd1 = du + t1;
if (d[v] > nd1)
{
d[v] = nd1;
pq.push({nd1, v});
}
long long nd2 = best[c] + sum[c] - w;
if (d[v] > nd2)
{
d[v] = nd2;
pq.push({nd2, v});
}
}
for (auto &e : g[u])
{
sum[e.c] = 0;
best[e.c] = INF;
}
}
if (d[n] == INF)
cout << -1;
else
cout << d[n];
}
