#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <utility>
#include <vector>
int main() {
using usize = std::size_t;
using u64 = std::uint64_t;
struct edge_type {
usize to;
u64 cost;
bool operator<(const edge_type &r) const { return cost > r.cost; }
};
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
usize N, M;
std::cin >> N >> M;
const usize ext_N = N + 2 * M;
std::vector<std::vector<edge_type>> graph(ext_N);
{
usize next_id = N;
std::map<std::pair<usize, usize>, usize> id_map;
const auto id = [&](const usize v, const usize c) -> usize {
const auto [itr, success] = id_map.insert({{v, c}, next_id});
if (success) {
next_id += 1;
}
return itr->second;
};
std::vector<u64> sum(ext_N, 0);
for (usize i = 0; i != M; i += 1) {
usize A, B, C;
u64 P;
std::cin >> A >> B >> C >> P;
A -= 1;
B -= 1;
for (usize t = 0; t != 2; t += 1) {
std::swap(A, B);
sum[id(A, C)] += P;
graph[A].push_back({B, P});
graph[A].push_back({id(B, C), 0});
graph[id(A, C)].push_back({B, -P});
}
}
for (const auto &[key, u] : id_map) {
const auto &[v, c] = key;
graph[v].push_back({u, 0});
for (edge_type &edge : graph[u]) {
edge.cost += sum[u];
}
}
}
static constexpr u64 Inf = std::numeric_limits<u64>::max();
std::vector<u64> dist(ext_N, Inf);
{
std::priority_queue<edge_type> que;
const auto push = [&](const usize v, const u64 d) -> void {
if (dist[v] > d) {
dist[v] = d;
que.push({v, d});
}
};
push(0, 0);
while (!que.empty()) {
const usize v = que.top().to;
const u64 d = que.top().cost;
que.pop();
if (dist[v] < d) {
continue;
}
for (const edge_type &edge : graph[v]) {
push(edge.to, d + edge.cost);
}
}
}
if (dist[N - 1] == Inf) {
std::cout << "-1\n";
} else {
std::cout << dist[N - 1] << "\n";
}
return 0;
}
