#include <bits/stdc++.h>
using namespace std;
using lli = long long;
template <class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const lli INF = 0x1f1f1f1f1f1f1f1f;
const int MAX_N = 1e5 + 7;
const int MAX_M = 2e5 + 7;
template <class T1, class T2>
inline constexpr bool minimise(T1 &x, T2 y) {
if (x > y) { x = y; return true; }
return false;
}
class Edge {
private:
int u, v, c;
lli w;
public:
Edge(int u = 0, int v = 0, int c = 0, lli w = 0): u(u), v(v), c(c), w(w) {}
inline lli cost() const { return w; }
inline pair<int, int> nodes() const { return make_pair(u, v); }
inline int other_node(int z) const { return u ^ v ^ z; }
inline int colour() const { return c; }
inline int get_node(bool is_rev) const { return is_rev ? v : u; }
inline bool is_start(int z) const { return z == u; }
};
int N, M;
Edge edge[MAX_M];
vector<int> adj[MAX_N];
void input() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int u, v, c; lli w;
cin >> u >> v >> c >> w;
edge[i] = Edge(u, v, c, w);
adj[u].push_back(i);
adj[v].push_back(i);
}
edge[M] = Edge(0, 1, M + 1, 0);
}
lli dist[MAX_M][2][2];
bool is_locked[MAX_M][2][2];
min_priority_queue<tuple<lli, int, bool, bool>> pq;
lli sum_colour[MAX_M];
lli solve() {
memset(dist, 0x1f, sizeof dist);
memset(is_locked, false, sizeof is_locked);
memset(sum_colour, 0, sizeof sum_colour);
auto relax = [&](int i, bool is_rev, bool is_prev_mod, lli d) {
if (minimise(dist[i][is_rev][is_prev_mod], d))
pq.emplace(d, i, is_rev, is_prev_mod);
};
relax(M, 0, 0, 0);
lli ans = INF;
while (not pq.empty()) {
lli cur_dist; int i; bool is_rev, is_prev_mod;
tie(cur_dist, i, is_rev, is_prev_mod) = pq.top();
pq.pop();
int v = edge[i].get_node(not is_rev);
if (v == N)
minimise(ans, cur_dist);
if (is_locked[i][is_rev][is_prev_mod])
continue;
is_locked[i][is_rev][is_prev_mod] = true;
for (int j : adj[v]) {
if (j == i and is_prev_mod)
continue;
int c = edge[j].colour();
sum_colour[c] += edge[j].cost();
}
for (int j : adj[v]) {
int c = edge[j].colour();
lli w = edge[j].cost();
bool new_is_rev = not edge[j].is_start(v);
if (sum_colour[c] == w)
relax(j, new_is_rev, false, cur_dist);
relax(j, new_is_rev, true, cur_dist + w);
relax(j, new_is_rev, false, cur_dist + sum_colour[c] - w);
}
for (int j : adj[v]) {
int c = edge[j].colour();
sum_colour[c] = 0;
}
}
if (ans >= INF)
ans = -1;
return ans;
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
input();
cout << solve();
return 0;
}
