// 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 index : adj[u]) {
int c = edges[index].c;
sum[u][c] += edges[index].p;
}
}
vector<vector<pair<int, ll>>> graph(n + 1);
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;
ll w = costu + costv;
graph[u].push_back({ v, w });
graph[v].push_back({ u, w });
}
vector<ll> distance(n + 1, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> stuff;
distance[1] = 0;
stuff.push({ 0, 1 });
while (!stuff.empty()) {
auto thing = stuff.top(); stuff.pop();
if (thing.first > distance[thing.second]) continue;
for (auto next : graph[thing.second]) {
if (distance[next.first] > distance[thing.second] + next.second) {
distance[next.first] = distance[thing.second] + next.second;
stuff.push({ distance[next.first], next.first });
}
}
}
if (distance[n] == INF) cout << "-1\n";
else cout << distance[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
