#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<ll, int> pli;
#define INF 1e18
#define pb push_back
struct cmp {
bool operator()(const vi &a, const vi &b) {
return a[0] > b[0];
}
};
void tc() {
int n, m;
cin >> n >> m;
vector<vector<int>> ed(n);
vector<vector<int>> edges(m);
vector<unordered_map<int, ll>> color_cost(n);
vector<vector<ll>> dp(m, vector<ll>(2, INF));
vector<vector<bool>> vis(m, vector<bool>(2, false));
for (int i = 0; i < m; ++i) {
int u, v, c;
ll p;
cin >> u >> v >> c >> p;
--u, --v;
edges[i] = {u, v, c, (int)p};
ed[u].pb(i);
ed[v].pb(i);
color_cost[u][c] += p;
color_cost[v][c] += p;
}
using state = tuple<ll, int, int, int>; // (cost, edge idx, node_side (0/1), is_fat)
priority_queue<state, vector<state>, greater<state>> pq;
for (int e : ed[0]) {
int u = edges[e][0], v = edges[e][1], c = edges[e][2];
ll p = edges[e][3];
int side = (u == 0) ? 0 : 1;
ll single = p;
ll group = color_cost[0][c] - p;
if (single < dp[e][0]) {
dp[e][0] = single;
pq.emplace(single, e, side, 0);
}
if (group < dp[e][1]) {
dp[e][1] = group;
pq.emplace(group, e, side, 1);
}
}
while (!pq.empty()) {
auto [cost, idx, side, fat] = pq.top();
pq.pop();
if (vis[idx][fat] || dp[idx][fat] != cost) continue;
vis[idx][fat] = true;
int node = edges[idx][side];
for (int e : ed[node]) {
if (e == idx) continue;
int next_side = (edges[e][0] == node) ? 0 : 1;
int col = edges[e][2];
ll p = edges[e][3];
ll group = color_cost[node][col] - p;
if (fat == 0 && edges[idx][2] == col)
group -= edges[idx][3];
group = max(group, 0LL);
if (dp[e][0] > cost + p) {
dp[e][0] = cost + p;
pq.emplace(cost + p, e, next_side, 0);
}
if (dp[e][1] > cost + group) {
dp[e][1] = cost + group;
pq.emplace(cost + group, e, next_side, 1);
}
}
}
ll ans = INF;
for (int e : ed[n - 1]) {
ans = min({ans, dp[e][0], dp[e][1]});
}
cout << (ans == INF ? -1 : ans) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
tc();
return 0;
}
