#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <climits>
using namespace std;
using ll = long long;
#define INF 1e18
#define MAXN 100001
struct Edge {
int to;
int color;
ll price;
};
int n, m;
vector<map<int, vector<Edge>>> adj(MAXN);
vector<ll> dp(MAXN, INT_MAX);
vector<map<int, ll>> dp2(MAXN);
vector<map<int, ll>> cum(MAXN);
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, color;
ll price;
cin >> u >> v >> color >> price;
adj[u][color].push_back({v, color, price});
adj[v][color].push_back({u, color, price});
cum[u][color] += price;
cum[v][color] += price;
}
dp[1] = 0;
priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
pq.push({0, {1, 0}});
while (!pq.empty()) {
ll price = pq.top().first;
int node = pq.top().second.first;
int color = pq.top().second.second;
pq.pop();
if (color != 0) {
if (dp2[node][color] != price) {
continue;
}
for (Edge next : adj[node][color]) {
// we can't flip edge in this case
ll opt1 = cum[node][color] + next.price;
if (opt1 + price < dp[next.to]) {
dp[next.to] = opt1 + price;
pq.push({dp[next.to], {next.to, 0}});
}
}
}
else {
if (dp[node] != price) {
continue;
}
for (auto& i : adj[node]) {
for (Edge j : i.second) {
// dont flip j
ll opt1 = cum[node][j.color] + j.price + price;
if (opt1 < dp[j.to]) {
dp[j.to] = opt1;
pq.push({dp[j.to], {j.to, 0}});
}
// flip j but not another edge of the same colour
ll opt2 = j.price + price;
if (opt2 < dp[j.to]) {
dp[j.to] = opt2;
pq.push({dp[j.to], {j.to, 0}});
}
// flip j and another edge of the same colour
ll opt3 = price;
if (!dp2[j.to].count(j.color) || opt3 < dp2[j.to][j.color]) {
dp2[j.to][j.color] = opt3;
pq.push({dp2[j.to][j.color], {j.to, j.color}});
}
}
}
}
}
if(dp[n] >= INF) {
cout << -1 << endl;
return 0;
}
cout << dp[n] << endl;
return 0;
}
