#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int dp[maxn];
vector<array<int, 3>> adj[maxn];
map<int,int> col[maxn], dpc[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> n >> m;
for (int i = 1, u, v, w, t; i <= m; i++)
{
cin >> u >> v >> w >> t;
adj[u].push_back({v, w, t});
adj[v].push_back({u, w, t});
if (col[u].count(w)) col[u][w] = -1;
else col[u][w] = 0;
if (col[v].count(w)) col[v][w] = -1;
else col[v][w] = 0;
}
for (int i = 1; i <= n; i++)
for (auto p : adj[i])
{
int &u = col[i][p[1]];
if (u == 0) continue;
if (u == -1) u = p[2];
else u += p[2];
}
priority_queue<ii, vector<ii>, greater<ii>> pq;
memset(dp, 0x3f, sizeof dp);
int oo = dp[0];
dp[1] = 0;
pq.emplace(0, 1);
while (pq.size())
{
int u, v;
tie(v, u) = pq.top();
pq.pop();
if (v != dp[u]) continue;
for (auto p : adj[u])
{
int color = p[1], cost = p[2], nxt = p[0];
if (col[u][color] != 0)
{
int val = v + cost, f = 0;
if (dp[nxt] > val)
dp[nxt] = val,
f = 1;
val = v + col[u][color] - cost;
if (dp[nxt] > val)
dp[nxt] = val,
f = 1,
dpc[nxt][color] = val - cost;
if (dpc[u].count(color))
{
val = dpc[u][color] + col[u][color] - cost;
if (dp[nxt] > val)
dp[nxt] = val,
f = 1,
dpc[nxt][color] = val - cost;
}
if (f) pq.emplace(dp[nxt], nxt);
}
else if (dp[nxt] > v)
dp[nxt] = v,
pq.emplace(dp[nxt], nxt);
}
}
cout << (dp[n] == oo ? -1 : dp[n]);
}
