/* ************************************************************************** */
/* */
/* ::: ::: ::: */
/* Problem Number: 20987 :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: js9028 <boj.kr/u/js9028> +#+ +#+ +#+ */
/* +#+ +#+ +#+ */
/* https://boj.kr/20987 #+# #+# #+# */
/* Solved: 2024/09/23 13:56:09 by js9028 ### ### ##.kr */
/* */
/* ************************************************************************** */
#include <bits/stdc++.h>
using namespace std;
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
typedef long long ll;
typedef long double lld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int MAXSIZE = 2000000;
const long long INF = 1e18 + 5;
const double EPSILON = 1e-14;
const ll DIV = 2000003;
const long double pi = 3.14159265358979323846264338327950288419716939937510L;
int n, m;
map<pair<int, int>, ll> clv; // (node, color) = sum
vector<array<int, 3>> adj[100055];
map<pair<int, int>, ll> color; // node, node color
map<pair<int, int>, ll> cost; //(node, node) cost
map<array<int, 3>, ll> dist; // (cur node, prv node) = dist
ll solve()
{
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
pq.push({0, 1, 0, 0});
dist[{1, 0, 0}] = 0;
while (!pq.empty())
{
auto &p = pq.top();
int cur = p[1], prv = p[2];
ll dis = p[0];
int u = p[3];
pq.pop();
if (cur == n)
return dis;
for (auto &nxt : adj[cur])
{
ll nd = dis + nxt[2];
if (dist.find({nxt[0], cur, 0}) == dist.end() || dist[{nxt[0], cur, 0}] > nd)
{
dist[{nxt[0], cur, 0}] = nd;
pq.push({nd, nxt[0], cur, 0});
}
if (u == 0)
{
nd = dis + clv[{cur, nxt[1]}] - nxt[2] - (nxt[1] == color[{cur, prv}] ? cost[{cur, prv}] : 0ll);
}
else
{
nd = dis + clv[{cur, nxt[1]}] - nxt[2];
}
if (dist.find({nxt[0], cur, 1}) == dist.end() || dist[{nxt[0], cur, 1}] > nd)
{
dist[{nxt[0], cur, 1}] = nd;
pq.push({nd, nxt[0], cur, 1});
}
}
}
return -1;
}
int main()
{
fastio;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c, p;
cin >> a >> b >> c >> p;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
clv[{a, c}] += p;
clv[{b, c}] += p;
cost[{a, b}] = p;
cost[{b, a}] = p;
color[{a, b}] = c;
color[{b, a}] = c;
}
cout << solve();
return 0;
}
