#include "bits/stdc++.h"
#include <queue>
#include <unordered_map>
using namespace std;
using ll = long long;
#define DEBUG 0
const ll INF = 1000'000'000'000'000'000ll;
const int MAXN = 100000;
const int MAXM = 200000;
int n, m;
unordered_map<int, int> s[MAXN + 5];
unordered_map<int, ll> csum[MAXN + 5];
int a[MAXN + 5][4];
struct edge {
int fr;
int to;
ll weight;
} e[4 * MAXM + 5];
vector<int> v[4 * MAXM + 5];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= m; i++) {
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
if (s[a[i][0]].find(0) == s[a[i][0]].end()) {
s[a[i][0]][0] = ++cnt;
}
if (s[a[i][0]].find(a[i][2]) == s[a[i][0]].end()) {
s[a[i][0]][a[i][2]] = ++cnt;
}
if (csum[a[i][0]].find(a[i][2]) == csum[a[i][0]].end()) {
csum[a[i][0]][a[i][2]] = a[i][3];
}
else csum[a[i][0]][a[i][2]] += a[i][3];
if (s[a[i][1]].find(0) == s[a[i][1]].end()) {
s[a[i][1]][0] = ++cnt;
}
if (s[a[i][1]].find(a[i][2]) == s[a[i][1]].end()) {
s[a[i][1]][a[i][2]] = ++cnt;
}
if (csum[a[i][1]].find(a[i][2]) == csum[a[i][1]].end()) {
csum[a[i][1]][a[i][2]] = a[i][3];
}
else csum[a[i][1]][a[i][2]] += a[i][3];
}
if (DEBUG) {
for (int i = 1; i <= n; i++) {
for (auto [dex, val] : s[i]) {
cout << "i: " << i << " col: " << dex << " index: " << val << endl;
}
}
}
int ecnt = 0;
for (int i = 1; i <= m; i++) {
int col = a[i][2];
int fr = a[i][0];
int to = a[i][1];
int node10 = s[fr][0];
int node1c = s[fr][col];
int node20 = s[to][0];
int node2c = s[to][col];
e[++ecnt] = {.fr = node10, .to = node20, .weight = (ll)a[i][3]};
v[node10].push_back(ecnt);
e[++ecnt] = {.fr = node20, .to = node10, .weight = (ll)a[i][3]};
v[node20].push_back(ecnt);
e[++ecnt] = {.fr = node10, .to = node1c, .weight = 0};
v[node10].push_back(ecnt);
e[++ecnt] = {.fr = node10, .to = node2c, .weight = 0};
v[node10].push_back(ecnt);
e[++ecnt] = {.fr = node20, .to = node1c, .weight = 0};
v[node20].push_back(ecnt);
e[++ecnt] = {.fr = node20, .to = node2c, .weight = 0};
v[node20].push_back(ecnt);
e[++ecnt] = {.fr = node1c, .to = node20, .weight = csum[fr][col] - a[i][3]};
v[node1c].push_back(ecnt);
e[++ecnt] = {.fr = node2c, .to = node10, .weight = csum[to][col] - a[i][3]};
v[node2c].push_back(ecnt);
}
if (DEBUG) {
for (int i = 1; i <= ecnt; i++) {
cout << "fr: " << e[i].fr << " to: " << e[i].to << " we: " << e[i].weight << endl;
}
}
int source = s[1][0];
int dest = s[n][0];
vector<ll> dist(cnt + 5, INF);
typedef pair<ll, int> pli;
priority_queue<pli, vector<pli>, greater<pli>> Q;
dist[source] = 0;
Q.push({0, source});
while (!Q.empty()) {
auto [curDist, cur] = Q.top();
Q.pop();
if (dist[cur] > curDist) continue;
if (cur == dest) break;
for (auto eg: v[cur]) {
if (dist[cur] + e[eg].weight < dist[e[eg].to]) {
dist[e[eg].to] = dist[cur] + e[eg].weight;
Q.push({dist[e[eg].to], e[eg].to});
}
}
}
if (DEBUG) {
for (int i = 1; i <= cnt; i++) {
cout << "dist " << i << " : " << dist[i] << endl;
}
}
if (dist[dest] == INF) dist[dest] = -1;
cout << dist[dest] << "\n";
}
