#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define Jungle "JOI21_ho_t4"
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define _(x) ((x) & -(x))
#define MASK(x) (1 << (x))
#define MULTEST \
int nq; \
cin >> nq; \
while (nq--)
template <typename T>
void chkmin(T &a, T b)
{
if (a > b)
a = b;
}
template <typename T>
void chkmax(T &a, T b)
{
if (a < b)
a = b;
}
const int mod = 1e9 + 7;
int add(int x, int y)
{
return (1ll * x + y) % mod;
}
int sub(int x, int y)
{
return (1ll * x - y + mod) % mod;
}
int mul(int x, int y)
{
return 1ll * x * y % mod;
}
const int maxn = 1e5, maxm = 2e5;
struct to
{
int v, c, p;
};
int n, m;
vector<to> adj[maxn + 2];
void init(void)
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u].push_back({v, c, p});
adj[v].push_back({u, c, p});
}
}
const long long inf = 2e18;
long long dp[maxn + 2], color[maxm + 2], sum[maxm + 2];
long long Dijkstra(const int source, const int sink)
{
for (int i = 1; i <= n; i++)
dp[i] = inf;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> store;
store.push({dp[source] = 0, source});
while (store.size())
{
const auto [d, u] = store.top();
if (u == sink)
return d;
store.pop();
if (dp[u] != d)
continue;
for (const auto [v, c, p] : adj[u])
{
sum[c] = 0;
color[c] = inf;
}
for (const auto [v, c, p] : adj[u])
{
sum[c] += p;
chkmin(color[c], dp[v]);
}
for (const auto [v, c, p] : adj[u])
{
long long val = min({d + p, d + sum[c] - p, color[c] + sum[c] - p});
if (dp[v] > val)
store.push({dp[v] = val, v});
}
}
return -1;
}
void solve(void)
{
init();
cout << Dijkstra(1, n);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
if (fopen(Jungle ".inp", "r"))
{
freopen(Jungle ".inp", "r", stdin);
freopen(Jungle ".out", "w", stdout);
}
// MULTEST
solve();
// cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
