#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll
using namespace std;
const int INF = 2e15;
struct nei {
int v, c, w;
};
int N, M;
vector<vector<nei>> graph;
vector<map<int, int>> color_cost;
class Compare {
public:
bool operator()(tuple<int, int, int, int> &a, tuple<int, int, int, int> &b) {
return get<0>(a) > get<0>(b);
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
graph.resize(N);
color_cost.resize(N);
for(int i = 0; i < M; i++) {
int a, b, c, w;
cin >> a >> b >> c >> w;
--a; --b; --c;
graph[a].push_back({b, c, w});
graph[b].push_back({a, c, w});
}
for(int i = 0; i < N; i++) {
for(nei& u : graph[i])
color_cost[i][u.c] += u.w;
}
vector<map<pii, int>> dist(N);
// wei, node, prev color, prev color weight
priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, Compare> q;
dist[0][{0, 0}] = 0;
q.push({0, 0, 0, 0});
while(!q.empty()) {
int w, v, pc, pw;
tie(w, v, pc, pw) = q.top(); q.pop();
for(nei& u : graph[v]) {
int opt1 = w + u.w;
if(!dist[u.v].count({u.c, u.w}) || dist[u.v][{u.c, u.w}] > opt1) {
dist[u.v][{u.c, u.w}] = opt1;
q.push({opt1, u.v, u.c, u.w});
}
int opt2 = w + color_cost[v][u.c] - u.w - (pc == u.c ? pw : 0);
if(!dist[u.v].count({0, 0}) || dist[u.v][{0, 0}] > opt2) {
dist[u.v][{0, 0}] = opt2;
q.push({opt2, u.v, 0, 0});
}
}
}
int mn = INF;
for(auto mp : dist[N - 1]) {
mn = min(mn, mp.second);
}
cout << (mn == INF ? -1 : mn) << endl;
}
