#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge
{
int v, c;
ll p;
};
struct Node
{
int v, c;
friend bool operator<(Node const& n1, Node const& n2)
{
return make_pair(n1.v, n1.c) < make_pair(n2.v, n2.c);
}
};
vector<vector<Edge>> g;
vector<map<int, vector<Edge>>> g_c;
vector<map<int, ll>> cost;
ll dijkstra()
{
Node s = {1, 0};
priority_queue<pair<ll, Node>, vector<pair<ll, Node>>, greater<pair<ll, Node>>> pq;
pq.push({0LL, s});
map<Node, ll> dist;
dist[s] = 0LL;
set<Node> processed;
while (!pq.empty())
{
auto[d, u] = pq.top();
pq.pop();
if (u.v == g.size()-1 && !u.c)
return d;
if (processed.count(u))
continue;
processed.insert(u);
if (u.c)
{
for (auto e : g_c[u.v][u.c])
{
Node v = {e.v, 0};
ll w = cost[u.v][u.c] - e.p;
if (!dist.count(v) || dist[u] + w < dist[v])
{
pq.push({dist[u] + w, v});
dist[v] = dist[u] + w;
}
}
}
else
{
for (auto e : g[u.v])
{
Node v = {e.v, 0};
ll w = min(e.p, cost[u.v][e.c] - e.p);
if (!dist.count(v) || dist[u] + w < dist[v])
{
pq.push({dist[u] + w, v});
dist[v] = dist[u] + w;
}
}
for (auto e : g[u.v])
{
Node v = {e.v, e.c};
ll w = 0;
if (!dist.count(v) || dist[u] + w < dist[v])
{
pq.push({dist[u] + w, v});
dist[v] = dist[u] + w;
}
}
}
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
g.resize(n+1);
g_c.resize(n+1);
cost.resize(n+1);
for (int i = 0; i < m; i++)
{
int a, b, c;
ll p;
cin >> a >> b >> c >> p;
cost[a][c] += p;
cost[b][c] += p;
g[a].push_back({b, c, p});
g[b].push_back({a, c, p});
g_c[a][c].push_back({b, c, p});
g_c[b][c].push_back({a, c, p});
}
ll ans = dijkstra();
cout << ans;
}
