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