#include<bits/stdc++.h>
using namespace std;
#define task "Robot"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;
const ll inf = 1e18 + 7;
int n, m, num, c[mxN * 2];
ll mn[mxN * 5], sum[mxN * 5], cost[mxN * 2];
vector<ii> w[mxN];
map<int, int> mp[mxN];
int nen(int j, int c)
{
if (j > n)
return j;
if (!mp[j][c])
mp[j][c] = ++num;
return mp[j][c];
}
void Dij(int j)
{
for (int i = 1; i <= num; i++)
mn[i] = inf;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, j});
mn[j] = 0;
while (pq.size())
{
ii j = pq.top();
pq.pop();
if (j.fi != mn[j.se])
continue;
for (ii i : w[j.se])
{
if (mn[i.fi] > j.fi + sum[nen(j.se, c[i.se])] - cost[i.se])
{
mn[i.fi] = j.fi + sum[nen(j.se, c[i.se])] - cost[i.se];
pq.push({mn[i.fi], i.fi});
}
if (j.se > n)
continue;
if (mn[i.fi] > j.fi + cost[i.se])
{
mn[i.fi] = j.fi + cost[i.se];
pq.push({mn[i.fi], i.fi});
}
if (mn[nen(i.fi, c[i.se])] > j.fi)
{
mn[nen(i.fi, c[i.se])] = j.fi;
pq.push({j.fi, nen(i.fi, c[i.se])});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen(task".INP", "r", stdin);
// freopen(task".OUT", "w", stdout);
cin >> n >> m;
num = n;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v >> c[i] >> cost[i];
w[u].push_back({v, i});
w[v].push_back({u, i});
sum[nen(u, c[i])] += cost[i];
w[nen(u, c[i])].push_back({v, i});
sum[nen(v, c[i])] += cost[i];
w[nen(v, c[i])].push_back({u, i});
}
Dij(1);
if (mn[n] == inf)
cout << -1;
else
cout << mn[n];
}
