//#pragma GCC optimize ("O3")
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include <cassert>
#include<algorithm>
#include <cstring>
#include<unordered_set>
#include<queue>
#include <array>
#include<cmath>
#include<unordered_map>
#include<queue>
#include <list>
#include <bitset>
using namespace std;
#define int long long
#define pii pair<int,int>
#define LL long long
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt”)
int INF = 1e18;
int n, m;
struct edge{
int destination, color_of_edge, price;
};
int dp[100001];
vector<vector<edge>>adj;
map<int, int> dp2[100001], colored_sum[100001];
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
adj = vector<vector<edge>>(n);
memset(dp, 0x3f, sizeof dp);
for(int i = 0; i < m; ++i){
int a, b, col, p;
cin >> a >> b >> col >> p;
--a;
--b;
adj[a].push_back({b, col, p});
adj[b].push_back({a, col, p});
colored_sum[a][col] += p;
colored_sum[b][col] += p;
}
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>>pq;
//dist, node, color of last edge recolored to reach here, IF YOU ARE IN DIST2 (if none that just 0 )
dp[0] = 0;
pq.push({0, {0, 0}});
while(!pq.empty()){
int d = pq.top().first;
auto [node, color_edge] = pq.top().second;
pq.pop();
if(color_edge == 0){
//normal dist
if(d > dp[node])
continue;
for(auto [dest, col, p] : adj[node]){
int takeneighbors = colored_sum[node][col] - p; //take neighbors
if(dp[dest] > d + takeneighbors){
dp[dest] = d + takeneighbors;
pq.push({dp[dest], {dest, 0}});
}
int takeyou = p;
if(dp[dest] > d + takeyou){
dp[dest] = d + takeyou;
pq.push({dp[dest], {dest, 0}});
}
if(!dp2[dest].count(col) || dp2[dest][col] > d){
dp2[dest][col] = d;
pq.push({dp2[dest][col], {dest, col}});
}
}
} else{
//dist2
if(d > dp2[node][color_edge])
continue;
//must take all neighbors except one
for(auto [dest, col, p] : adj[node]){
if(col != color_edge)
continue;
int takeneighbors = colored_sum[node][col] - p;
if(dp[dest] > d + takeneighbors){
dp[dest] = d + takeneighbors;
pq.push({dp[dest], {dest, 0}});
}
}
}
}
if(dp[n - 1] == INF){
cout << -1;
return 0;
}
cout << dp[n - 1];
//find ans for dp[n-1]
}
