#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>
using std::cout;
using std::endl;
using std::vector;
using std::pair;
struct Road {
int to;
int color;
int change_cost;
};
// https://oj.uz/problem/view/JOI21_ho_t4 (input ommitted due to length)
int main() {
int crossing_num;
int road_num;
std::cin >> crossing_num >> road_num;
vector<vector<Road>> neighbors(crossing_num);
vector<std::unordered_map<int, long long>> color_sums(crossing_num);
for (int r = 0; r < road_num; r++) {
int from;
int to;
int color;
int change_cost;
std::cin >> from >> to >> color >> change_cost;
neighbors[--from].push_back({--to, color, change_cost});
neighbors[to].push_back({from, color, change_cost});
color_sums[from][color] += change_cost;
color_sums[to][color] += change_cost;
}
vector<std::unordered_map<int, long long>> min_cost(crossing_num);
min_cost[0][-1] = 0;
// a "node" will be represented as a position and the last color change (-1 if no change) along with its cost
std::priority_queue<pair<long long, pair<int, pair<int, int>>>> frontier;
frontier.push({0, {0, {-1, 0}}});
while (!frontier.empty()) {
auto [at, prev_c] = frontier.top().second;
long long curr_cost = min_cost[at][prev_c.first];
if (-frontier.top().first != curr_cost) {
frontier.pop();
continue;
}
if (at == crossing_num - 1) {
cout << curr_cost << endl;
goto end;
}
frontier.pop();
for (const Road& r : neighbors[at]) {
long long change_this = curr_cost + r.change_cost;
if (min_cost[r.to].find(r.color) == min_cost[r.to].end() || change_this < min_cost[r.to][r.color]) {
min_cost[r.to][r.color] = change_this;
frontier.push({-change_this, {r.to, {r.color, r.change_cost}}});
}
long long change_others = curr_cost + color_sums[at][r.color] - r.change_cost;
if (prev_c.first == r.color) {
change_others -= prev_c.second;
}
if (min_cost[r.to].find(-1) == min_cost[r.to].end() || change_others < min_cost[r.to][-1]) {
min_cost[r.to][-1] = change_others;
frontier.push({-change_others, {r.to, {-1, 0}}});
}
}
}
cout << -1 << endl;
end:;
}
