#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;
const int MAX = 200007;
vector<pii> G[MAX];
ll C[MAX], P[MAX], D[MAX];
ll Dijkstra(int col, int N) {
memset(D, 0x3f, sizeof(D));
priority_queue<pii, vector<pii>, greater<pii>> PQ;
PQ.emplace(D[1] = 0, 1);
while (!PQ.empty()) {
auto [cd, cur] = PQ.top(); PQ.pop();
for (auto [next, en] : G[cur]) {
ll nd = (C[en] == col ? 0LL : P[en]);
if (cd + nd >= D[next]) continue;
PQ.emplace(D[next] = cd + nd, next);
}
}
ll ret = 0;
for (int i = 1; i <= N; ++i) ret = max(ret, D[i]);
return ret;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, M;
cin >> N >> M;
vector<int> col;
for (int i = 0; i < M; ++i) {
ll a, b;
cin >> a >> b >> C[i] >> P[i];
G[a].emplace_back(b, i);
G[b].emplace_back(a, i);
col.push_back(C[i]);
}
ll ans = 2e18;
for (int c : col) ans = min(ans, Dijkstra(c, N));
cout << (ans > 1e18 ? -1LL : ans);
return 0;
}
