// JOI_2021.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Edge {
int u, v, c;
ll p;
};
int main() {
int n, m;
cin >> n >> m;
vector<Edge> edges(m);
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].c >> edges[i].p;
adj[edges[i].u].push_back(i);
adj[edges[i].v].push_back(i);
}
vector<map<int, ll>> sum(n + 1);
for (int u = 1; u <= n; u++) {
for (int idx : adj[u]) {
sum[u][edges[idx].c] += edges[idx].p;
}
}
map<pair<int, int>, int> id;
int nxt = n + 1;
auto getid = [&](int u, int c) {
pair<int, int> key = { u, c };
if (!id.count(key)) {
id[key] = nxt++;
}
return id[key];
};
vector<vector<pair<int, ll>>> graph(n + 2 * m + 5);
for (int i = 0; i < m; i++) {
int u = edges[i].u;
int v = edges[i].v;
int c = edges[i].c;
ll p = edges[i].p;
ll costu = sum[u][c] - p;
ll costv = sum[v][c] - p;
int uc = getid(u, c);
int vc = getid(v, c);
graph[u].push_back({ v, p });
graph[v].push_back({ u, p });
graph[u].push_back({ v, costu });
graph[v].push_back({ u, costv });
graph[u].push_back({ vc, 0 });
graph[v].push_back({ uc, 0 });
graph[uc].push_back({ v, costu });
graph[vc].push_back({ u, costv });
}
int total_nodes = nxt;
vector<ll> dist(total_nodes, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> stuff;
dist[1] = 0;
stuff.push({ 0, 1 });
while (!stuff.empty()) {
auto thing = stuff.top();
stuff.pop();
if (thing.first > dist[thing.second]) continue;
for (auto next : graph[thing.second]) {
if (dist[next.first] > thing.first + next.second) {
dist[next.first] = thing.first + next.second;
stuff.push({ dist[next.first], next.first });
}
}
}
if (dist[n] == INF) cout << -1 << '\n';
else cout << dist[n] << '\n';
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
