#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<map<int, vector<pair<ll, pair<int, int>>>>> adjacency(n + 1);
vector<map<int, ll>> sumOfColour(n + 1), dp(n + 1);
vector<ll> dist(n + 1, INF);
for (int i = 0; i < m; ++i) {
int a, b, c;
ll p;
cin >> a >> b >> c >> p;
adjacency[a][c].push_back({p, {b, c}});
adjacency[b][c].push_back({p, {a, c}});
sumOfColour[a][c] += p;
sumOfColour[b][c] += p;
}
priority_queue<pair<ll, pair<int, int>>> pq;
dist[1] = 0;
pq.push({0, {1, 0}});
while (!pq.empty()) {
auto [curCost, curAndColour] = pq.top();
pq.pop();
auto [cur, colour] = curAndColour;
if (colour) {
if (dp[cur][colour] != -curCost) continue;
for (auto &edge : adjacency[cur][colour]) {
ll curCase = sumOfColour[cur][colour] - edge.first - curCost;
if (curCase < dist[edge.second.first]) {
dist[edge.second.first] = curCase;
pq.push({-curCase, {edge.second.first, 0}});
}
}
} else if (-curCost == dist[cur]) {
for (auto &c : adjacency[cur]) {
for (auto &edge : c.second) {
ll curCase = sumOfColour[cur][edge.second.second] -
edge.first - curCost;
if (curCase < dist[edge.second.first]) {
dist[edge.second.first] = curCase;
pq.push({-curCase, {edge.second.first, 0}});
}
curCase = edge.first - curCost;
if (curCase < dist[edge.second.first]) {
dist[edge.second.first] = curCase;
pq.push({-curCase, {edge.second.first, 0}});
}
curCase = -curCost;
if (!dp[edge.second.first].count(edge.second.second) ||
curCase < dp[edge.second.first][edge.second.second]) {
dp[edge.second.first][edge.second.second] = curCase;
pq.push({-curCase,
{edge.second.first, edge.second.second}});
}
}
}
}
}
cout << (dist[n] == INF ? -1 : dist[n]) << endl;
return 0;
}
