#include <bits/stdc++.h>
/*
Brute to win
*/
using namespace std;
using ll = long long;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;
int n, m;
vector <pii> adj[N];
int c[N], p[N];
int dp1[N]; // xet den u, type = 0/1 la co thay doi toan bo canh cung mau hay ko
map <int, int> dp2[N], pfs[N];
struct item {
int c, u, type;
bool operator <(const item &other) const {
return c > other.c;
}
};
void dijk() {
for (int i = 1; i <= n; i++) {
dp1[i] = inf;
}
for (int i = 1; i <= n; i++) {
for (auto [v, id] : adj[i]) {
dp2[i][c[id]] = inf;
}
}
dp1[1] = 0;
priority_queue <item> q;
q.push({0, 1, 0});
while(q.size()) {
auto [val, u, type] = q.top();
q.pop();
if (type == 0) {
if (val > dp1[u]) continue;
for (auto [v, id] : adj[u]) {
if (dp1[v] > dp1[u] + p[id]) {
dp1[v] = dp1[u] + p[id];
q.push({dp1[v], v, 0});
}
if (dp1[v] > dp1[u] + pfs[u][c[id]] - p[id]) {
dp1[v] = dp1[u] + pfs[u][c[id]] - p[id];
q.push({dp1[v], v, 0});
}
if (dp2[v][c[id]] > dp1[u]) {
dp2[v][c[id]] = dp1[u];
q.push({dp2[v][c[id]], v, c[id]});
}
}
}
else {
for (auto [v, id] : adj[u]) {
if (c[id] != type) continue;
if (dp1[v] > dp2[u][type] + pfs[u][c[id]] - p[id]) {
dp1[v] = dp2[u][type] + pfs[u][c[id]] - p[id];
q.push({dp1[v], v, 0});
}
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v >> c[i] >> p[i];
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
for (int i = 1; i <= n; i++) {
for (auto [v, id] : adj[i]) {
pfs[i][c[id]] += p[id];
}
}
dijk();
cout << (dp1[n] >= inf ? -1 : dp1[n]);
return 0;
}
