#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);
}
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<unordered_map<int, int>> cnt;
vector<unordered_map<int, ll>> cost;
ll dijkstra()
{
vector<Node> nodes = {{1, 0, false, 0, 0LL}};
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0LL, 0});
vector<vector<unordered_map<int, ll>>> dist(2, vector<unordered_map<int, ll>>(g.size()));
dist[0][1][0] = 0LL;
vector<vector<unordered_set<int>>> processed(2, vector<unordered_set<int>>(g.size()));
while (!pq.empty())
{
auto[d, idx] = pq.top();
pq.pop();
Node u = nodes[idx];
if (u.v == g.size()-1)
return d;
if (processed[u.changed][u.v].count(u.from))
continue;
processed[u.changed][u.v].insert(u.from);
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[v.changed][v.v].count(v.from) || dist[u.changed][u.v][u.from] + w < dist[v.changed][v.v][v.from])
{
pq.push({dist[u.changed][u.v][u.from] + w, nodes.size()});
nodes.push_back(v);
dist[v.changed][v.v][v.from] = dist[u.changed][u.v][u.from] + 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[v.changed][v.v].count(v.from) || dist[u.changed][u.v][u.from] + w < dist[v.changed][v.v][v.from])
{
pq.push({dist[u.changed][u.v][u.from] + w, nodes.size()});
nodes.push_back(v);
dist[v.changed][v.v][v.from] = dist[u.changed][u.v][u.from] + 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;
}
