#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
void setIO(string name) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!name.empty()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
struct edge {
int u, v, c, p;
edge (int _u=0, int _v=0, int _c=0, int _p=0) : u(_u), v(_v), c(_c), p(_p) {}
int oth(int node) { return node ^ u ^ v; }
};
struct state {
ll cost;
int u, need, i;
state(ll _c=0, int _u=0, int _need=0, int _i=0) : cost(_c), u(_u), i(_i), need(_need) {}
friend bool operator < (const state &a, const state &b) {
return a.cost > b.cost;
}
};
const ll LINF = 1e15;
const int N = 1e5+5;
const int M = 2e5+5;
int n, m;
edge e[M];
vector<int> graph[N], color[N];
vector<ll> dp[N][2], sum[N];
int get(vector<int> &v, int i) {
return lower_bound(all(v), i) - v.begin();
}
int main() {
setIO("");
cin >> n >> m;
foru(i, 1, m) {
int u, v, c, p;
cin >> u >> v >> c >> p;
e[i] = edge(u, v, c, p);
graph[u].push_back(i);
graph[v].push_back(i);
color[u].push_back(c);
color[v].push_back(c);
}
foru(i, 1, n) {
dp[i][0].resize(sz(graph[i]), LINF);
dp[i][1].resize(sz(graph[i]), LINF);
sort(all(color[i]));
color[i].resize(unique(all(color[i])) - color[i].begin());
sum[i].resize(color[i].size(), 0);
}
foru(i, 1, m) {
sum[e[i].u][get(color[e[i].u], e[i].c)] += e[i].p;
sum[e[i].v][get(color[e[i].v], e[i].c)] += e[i].p;
}
priority_queue<state> pq;
pq.push(state(0, 1, -1, -1));
while (!pq.empty()) {
state at = pq.top(); pq.pop();
int u = at.u, lst = at.i, need = at.need;
// if (lst != -1) cout << at.cost << " " << u << " " << e[graph[u][lst]].oth(u) << " " << need << "\n";
if (u == n) break;
if (lst != -1 && dp[u][need][lst] != at.cost) continue;
foru(i, 0, sz(graph[u])-1) {
if (i == lst) continue;
int idx = graph[u][i];
int v = e[idx].oth(u);
int kth = get(graph[v], idx), kthcolor = get(color[u], e[idx].c);
ll cost;
if (sum[u][kthcolor] == e[idx].c) {
if (dp[v][0][kth] > at.cost) {
dp[v][0][kth] = at.cost;
pq.push(state(at.cost, v, 0, kth));
}
continue;
}
cost = at.cost + e[idx].p;
if (dp[v][1][kth] > cost) {
dp[v][1][kth] = cost;
pq.push(state(cost, v, 1, kth));
}
cost = at.cost + sum[u][kthcolor] - e[idx].p;
if (lst != -1 && e[graph[u][lst]].c == e[idx].c && need) {
cost -= e[graph[u][lst]].p;
}
if (dp[v][0][kth] > cost) {
dp[v][0][kth] = cost;
pq.push(state(cost, v, 0, kth));
}
}
}
ll ans = LINF;
foru(i, 0, sz(graph[n])-1) ans = min(ans, min(dp[n][0][i], dp[n][1][i]));
cout << (ans == LINF ? -1 : ans);
}
