#include <bits/stdc++.h>
using namespace std;
using lli = long long;
/*How to use:
Tvector <int, 2> g(n); //graph
Tvector <int, 3> f(n, k, 2) = f[n][k][2]
*/
template <class Tp, int D = 1>
struct Tvector : public vector<Tvector<Tp, D - 1>> {
template <class... Args>
Tvector(int n = 0, Args... args) : vector<Tvector<Tp, D - 1>>(n, Tvector<Tp, D - 1>(args...)) {}
};
template <class Tp>
struct Tvector<Tp, 1> : public vector<Tp> {
Tvector(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {}
};
#ifdef LOCAL
#include </home/marcus06/mycp/Library/debug.h>
#else
#define debug(...)
#endif
const int INF = int(1e9) + 7;
void solve() {
int N, M;
cin >> N >> M;
Tvector <array <int, 3>, 2> graph(N);
vector <map <int, lli>> cost(N);
vector <map <int, pair <int, int>>> edge_info(N);
for (int i = 0; i < M; ++i) {
int A, B, C, P;
cin >> A >> B >> C >> P;
--A, --B;
cost[A][C] += P;
cost[B][C] += P;
edge_info[A][B] = edge_info[B][A] = {C, P};
graph[A].push_back({B, C, P});
graph[B].push_back({A, C, P});
}
vector <map <pair <int, int>, lli>> dist(N);
priority_queue <array <lli, 4>> Q;
Q.push({0, 0, INF, 0});
dist[0][{INF, 0}] = 0;
while (!Q.empty()) {
auto [d, u, color, parent] = Q.top(); Q.pop();
d = -d;
if (d > dist[u][{color, parent}]) continue;
for (auto [v, nxt_color, price]: graph[u]) {
if (dist[v].find({INF, u}) == dist[v].end() || dist[v][{INF, u}] > d + price) {
dist[v][{INF, u}] = d + price;
Q.push({-dist[v][{INF, u}], v, INF, u});
}
lli w = cost[u][nxt_color] - price;
if (color == INF) {
auto [C, P] = edge_info[u][parent];
if (nxt_color == C) w -= P;
}
if (w < 0) continue;
if (dist[v].find({nxt_color, u}) == dist[v].end() || dist[v][{nxt_color, u}] > d + w) {
dist[v][{nxt_color, u}] = d + w;
Q.push({-dist[v][{nxt_color, u}], v, nxt_color, u});
}
}
}
lli ans = lli(1e18) + 7;
for (auto itr: dist[N - 1]) {
ans = min(ans, itr.second);
}
if (dist[N - 1].empty()) ans = -1;
cout << ans << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
auto begin = std::chrono::high_resolution_clock::now();
#endif
int tt = 1;
while (tt--) {
solve();
}
#ifdef LOCAL
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
return 0;
}
