#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
#define FOR(i, N) for (int i = 0; i < N; i++)
#define ll long long
const int MAX_N = 1e5 + 5;
const int MAX_M = 2e5 + 5;
const ll oo = 1LL << 60;
struct Edge {
int id;
int nextNode;
int color;
int cost;
Edge(int i, int b, int c, int p) {
id = i;
nextNode = b;
color = c;
cost = p;
}
};
int edgeColors[MAX_M];
int N, M;
vector <Edge> adj[MAX_N];
unordered_map<int, int> adjColors[MAX_N];
unordered_map<ll, ll> dp;
ll solve(int node, int prevEdge, bool recolored) {
if (node == N - 1) {
return 0;
}
ll key = 0;
key += node;
key *= MAX_M;
key += 1 + prevEdge;
key *= 2;
key += recolored;
if (dp.find(key) != dp.end()) {
return dp[key];
}
ll ans = oo;
for (Edge& e : adj[node]) {
if (e.id == prevEdge)continue;
int colorCount = adjColors[node][e.color];
if (recolored && edgeColors[prevEdge] == e.color) {
colorCount--;
}
if (colorCount == 1) {
ans = min(ans, solve(e.nextNode, e.id, false));
}
else {
ans = min(ans, solve(e.nextNode, e.id, true) + e.cost);
}
}
dp[key] = ans;
return ans;
}
struct State {
int node, prevEdge;
bool recolored;
ll dist;
State(int n, int p, bool r, ll c) {
node = n;
prevEdge = p;
recolored = r;
dist = c;
}
};
struct Compare {
bool operator() (State& a, State& b) {
return a.dist > b.dist;
}
};
priority_queue<State, std::vector<State>, Compare> pq;
inline void add(int node, int prevEdge, bool recolored, ll dist) {
ll key = 0;
key += node;
key *= MAX_M;
key += 1 + prevEdge;
key *= 2;
key += recolored;
if (dp.find(key) == dp.end() || dp[key] > dist) {
dp[key] = dist;
pq.push(*new State(node, prevEdge, recolored, dist));
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M;
FOR(i, M) {
int a, b, c, p;
cin >> a >> b >> c >> p;
a--;
b--;
adj[a].push_back(*new Edge(i, b, c, p));
adjColors[a][c]++;
adj[b].push_back(*new Edge(i, a, c, p));
adjColors[b][c]++;
edgeColors[i] = c;
}
//ll ans = solve(0, -1, 0);
//if (ans >= oo) {
// ans = -1;
//}
//cout << ans;
pq.push(*new State(0, -1, 0, 0));
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
if (cur.node == N - 1) {
cout << cur.dist << "\n";
return 0;
}
ll key = 0;
key += cur.node;
key *= MAX_M;
key += 1 + cur.prevEdge;
key *= 2;
key += cur.recolored;
if (dp[key] < cur.dist)continue;
for (Edge& e : adj[cur.node]) {
if (e.id == cur.prevEdge)continue;
int colorCount = adjColors[cur.node][e.color];
if (cur.recolored && edgeColors[cur.prevEdge] == e.color) {
colorCount--;
}
if (colorCount == 1) {
add(e.nextNode, e.id, false, cur.dist);
}
else {
add(e.nextNode, e.id, true, cur.dist + e.cost);
}
}
}
cout << -1;
}
