#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<map<int, vector<tuple<int, int, long long>>>> edges(n);
vector<map<int, long long>> price_sums(n);
for (int i = 0; i < m; i++){
int a, b, c;
long long p;
cin >> a >> b >> c >> p;
a--, b--;
edges[a][c].push_back({b, c, p});
edges[b][c].push_back({a, c, p});
price_sums[a][c] += p;
price_sums[b][c] += p;
}
vector<long long> dist(n, INF);
vector<map<int, long long>> dist2(n);
priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> frontier;
dist[0] = 0;
frontier.push({0, 0, 0});
while (!frontier.empty()){
int curr = get<1>(frontier.top());
int curr_color = get<2>(frontier.top());
long long curr_dist = get<0>(frontier.top());
frontier.pop();
if (curr_color > 0){
if (dist2[curr][curr_color] != curr_dist) continue;
for (const auto &edge : edges[curr][curr_color]){
int node = get<0>(edge);
long long price = get<2>(edge);
long long case1 = curr_dist + price_sums[curr][curr_color] - price;
if (dist[node] > case1){
dist[node] = case1;
frontier.push({dist[node], node, 0});
}
}
}
else {
if (dist[curr] != curr_dist) continue;
for (const auto &adj : edges[curr]){
for (const auto &edge : adj.second){
int node = get<0>(edge);
int color = get<1>(edge);
long long price = get<2>(edge);
long long case1 = curr_dist + price_sums[curr][color] - price;
if (dist[node] > case1){
dist[node] = case1;
frontier.push({dist[node], node, 0});
}
long long case2 = curr_dist + price;
if (dist[node] > case2){
dist[node] = case2;
frontier.push({dist[node], node, 0});
}
long long case3 = curr_dist;
if (dist2[node].count(color) == 0 || dist2[node][color] > case3){
dist2[node][color] = case3;
frontier.push({dist2[node][color], node, color});
}
}
}
}
}
cout << (dist[n - 1] >= INF ? -1 : dist[n - 1]);
return 0;
}
