#include <bits/stdc++.h>
#define ll long long
#define pr pair <ll, int>
#define fi first
#define se second
using namespace std;
const ll inf = 1e18;
const int N = 1e5 + 5;
map <int, ll> sum[N], dc[N];
map <int, vector<pr>> a[N];
int n, m;
ll res, d[N];
struct haha
{
ll dist;
int to, color;
};
struct cmp
{
bool operator() (const haha &a, const haha &b)
{
return a.dist > b.dist;
}
};
void inp()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, c;
ll w;
cin >> x >> y >> c >> w;
a[x][c].push_back({w, y});
a[y][c].push_back({w, x});
sum[x][c] += w;
sum[y][c] += w;
// cout << sum[4][3] << "\n";
}
}
void dijkstra()
{
priority_queue <haha, vector<haha>, cmp> q;
q.push({0, 1, 0});
for (int i = 1; i <= n; i++)
d[i] = inf;
d[1] = 0;
while (!q.empty())
{
int u = q.top().to, color = q.top().color;
ll k = q.top().dist;
q.pop();
//cout << u << " " << color << " " << k << "\n";
if (!color && k != d[u])
continue;
if (color && k != dc[u][color])
continue;
if (color == 0)
{
for (auto &i : a[u])
{
for (auto &j : i.se)
{
int v = j.se;
ll w = j.fi;
if (d[v] > k + w)
{
d[v] = k + w;
q.push({d[v], v, 0});
}
ll val = d[u] + sum[u][i.fi] - w;
if (d[v] > d[u] + sum[u][i.fi] - w)
{
q.push({val, v, 0});
d[v] = val;
}
if (!dc[v].count(i.fi) || dc[v][i.fi] > k)
{
dc[v][i.fi] = k;
// cout << sum[u][i.fi] - w << " " << u << " " << v << " " << i.fi << "\n";
q.push({k, v, i.fi});
}
}
}
}
else
{
for (pr i : a[u][color])
{
int v = i.se;
ll w = i.fi;
ll val = k + sum[u][color] - w;
if (d[v] > val)
{
d[v] = val;
q.push({val, v, 0});
}
}
}
}
}
void solve()
{
dijkstra();
res = d[n];
for (auto &i : dc[n])
res = min(res, i.se);
cout << (res == inf ? -1 : res);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
inp();
solve();
}
