#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
struct Edge
{
int to, c;
ll p;
};
map<int, vector<Edge>> graph[100001];
ll dp[100001];
map<int, ll> dp2[100001], psum[100001];
int main()
{
int N, M;
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int u, v, c;
ll p;
cin >> u >> v >> c >> p;
graph[u][c].push_back({v, c, p});
graph[v][c].push_back({u, c, p});
psum[u][c] += p;
psum[v][c] += p;
}
for (int i = 0; i <= N; i++)
dp[i] = LONG_LONG_MAX;
dp[1] = 0;
using T = tuple<ll, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, 1, 0});
while (!pq.empty())
{
ll cost;
int node, c;
tie(cost, node, c) = pq.top();
pq.pop();
if (c)
{
if (dp2[node][c] != cost)
continue;
for (Edge i : graph[node][c])
{
ll case1 = psum[node][c] - i.p + cost;
if (case1 < dp[i.to])
{
dp[i.to] = case1;
pq.push({dp[i.to], i.to, 0});
}
}
}
else
{
if (dp[node] != cost)
continue;
for (auto &i : graph[node])
{
for (Edge j : i.second)
{
ll case1 = psum[node][j.c] - j.p + cost;
if (case1 < dp[j.to])
{
dp[j.to] = case1;
pq.push({dp[j.to], j.to, 0});
}
ll case2 = j.p + cost;
if (case2 < dp[j.to])
{
dp[j.to] = case2;
pq.push({dp[j.to], j.to, 0});
}
ll case3 = cost;
if (!dp2[j.to].count(j.c) || case3 < dp2[j.to][j.c])
{
dp2[j.to][j.c] = case3;
pq.push({dp2[j.to][j.c], j.to, j.c});
}
}
}
}
}
cout << (dp[N] == LONG_LONG_MAX ? -1 : dp[N]) << '\n';
return 0;
}
