#include <bits/stdc++.h>
#include <queue>
using namespace std;
struct edge {
int to, c, id;
long long p;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<edge>> graph(n);
vector<map<int, long long>> color(n);
vector<map<int, int>> vis(n);
vector<edge> edges;
vector<map<int, long long>> dis(n);
for (int i = 0; i < m; i++) {
int a, b, c; long long p;
cin >> a >> b >> c >> p;
a--, b--;
edge e1; edge e2;
e1.id = i * 2; e2.id = i * 2 + 1;
e1.to = b; e2.to = a; e1.c = e2.c = c; e1.p = e2.p = p;
graph[a].push_back(e1); graph[b].push_back(e2);
edges.push_back(e1); edges.push_back(e2);
}
for (int i = 0; i < n; i++) {
for (auto eg : graph[i]) {
color[i][eg.c] += eg.p;
}
}
dis[0][-1] = 0;
priority_queue<pair<long long, pair<int, int>>> pq;
pq.push({0, {0, -1}});
while (pq.size() > 0) {
auto t = pq.top();
pq.pop();
if (vis[t.second.first][t.second.second]) {
continue;
}
vis[t.second.first][t.second.second] = 1;
long long d = dis[t.second.first][t.second.second];
for (auto eg: graph[t.second.first]) {
long long cost = color[t.second.first][eg.c];
if (t.second.second >= 0 && eg.c == edges[t.second.second].c) {
cost -= edges[t.second.second].p;
}
if (dis[eg.to].find(-1) == dis[eg.to].end() || d + cost - eg.p < dis[eg.to][-1]) {
dis[eg.to][-1] = d + cost - eg.p;
pq.push({-dis[eg.to][-1], {eg.to, -1}});
}
if (dis[eg.to].find(eg.id) == dis[eg.to].end() || d + eg.p < dis[eg.to][eg.id]) {
dis[eg.to][eg.id] = d + eg.p;
pq.push({-dis[eg.to][eg.id], {eg.to, eg.id}});
}
}
}
long long md = 1e18;
for (auto it = dis[n - 1].begin(); it != dis[n - 1].end(); it++) {
md = min(md, it->second);
}
if (md == 1e18) {
cout << "-1\n";
} else {
cout << md << "\n";
}
}
