#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 edgeCosts[MAX_M];
int N, M;
vector <Edge> adj[MAX_N];
unordered_map<int, ll> adjColors[MAX_N];
unordered_map<ll, ll> dp;
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] += p;
adj[b].push_back(*new Edge(i, a, c, p));
adjColors[b][c] += p;
edgeColors[i] = c;
edgeCosts[i] = p;
}
add(0, -1, 0, 0);
ll ans = oo;
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
ll key = 0;
key += cur.node;
key *= MAX_M;
key += 1 + cur.prevEdge;
key *= 2;
key += cur.recolored;
if (dp[key] < cur.dist)continue;
if (cur.node == N - 1) {
ans = min(ans, cur.dist);
}
for (Edge& e : adj[cur.node]) {
if (e.id == cur.prevEdge)continue;
ll colorCost = adjColors[cur.node][e.color];
colorCost -= e.cost;
if (cur.recolored && edgeColors[cur.prevEdge] == e.color) {
colorCost -= edgeCosts[cur.prevEdge];
}
add(e.nextNode, e.id, false, cur.dist + colorCost);
add(e.nextNode, e.id, true, cur.dist + e.cost);
}
}
if (ans == oo)ans = -1;
cout << ans;
}
