#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;
int n, m;
vector<pii> adj[N];
int c[N], p[N];
int dp1[N];
map<int,int> dp2[N], pfs[N];
map<int, vector<pii>> adj1[N];
struct item {
int val, u, type;
bool operator<(const item &o) const {
return val > o.val;
}
};
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.empty()) {
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 {
if (val > dp2[u][type]) continue;
for (auto [v,id] : adj1[u][type]) {
if (dp1[v] > dp2[u][type] + pfs[u][type] - p[id]) {
dp1[v] = dp2[u][type] + pfs[u][type] - 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);
adj1[u][c[i]].emplace_back(v,i);
adj1[v][c[i]].emplace_back(u,i);
pfs[u][c[i]] += p[i];
pfs[v][c[i]] += p[i];
}
dijk();
cout << (dp1[n] >= inf ? -1 : dp1[n]);
return 0;
}
