#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
struct Edge
{
int v, c;
ll p;
};
struct Node
{
int v, from, c;
ll p;
friend bool operator==(Node const& n1, Node const& n2)
{
return make_tuple(n1.v, n1.from) == make_tuple(n2.v, n2.from);
}
friend bool operator<(Node const& n1, Node const& n2)
{
return make_tuple(n1.v, n1.from) < make_tuple(n2.v, n2.from);
}
};
struct NodeHash
{
size_t operator()(Node const& n) const
{
size_t h = 0;
h ^= std::hash<int>{}(n.v) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
h ^= std::hash<int>{}(n.from) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
h ^= std::hash<int>{}(n.c) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
h ^= std::hash<long long>{}(n.p)+ 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
return h;
}
};
vector<vector<Edge>> g;
vector<unordered_map<int, int>> cnt;
vector<unordered_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, 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.find(u) != processed.end())
continue;
processed.insert(u);
ll d_u = dist[u];
for (auto e : g[u.v])
{
if (e.v == u.from)
continue;
ll w = e.p;
Node v = {e.v, u.v, e.c, e.p};
if (dist.find(v) == dist.end() || d_u + w < dist[v])
{
pq.push({d_u + w, v});
dist[v] = d_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, 0, 0LL};
if (dist.find(v) == dist.end() || d_u + w < dist[v])
{
pq.push({d_u + w, v});
dist[v] = d_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<unordered_map<int, int>>(n+1);
cost = vector<unordered_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;
}
