//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;
typedef tuple<int, int, int> F;
void solve(){
int n, m; cin >> n >> m;
vector<map<int, vector<T>>>g(n+1);
vector<map<int, int>>dp(n+1), sum(n+1);
for (int i = 0; i<m; i++){
int a, b, c, p; cin >> a >> b >> c >> p;
g[a][c].emplace_back(b, p);
g[b][c].emplace_back(a, p);
dp[a][c] = oo;
dp[b][c] = oo;
sum[a][c] += p;
sum[b][c] += p;
}
// if (m == 1){
// for (auto [x, c, p]: g[1]){
// if (x == n){
// cout << "0\n";
// return;
// }
// }
// cout << "-1\n";
// return;
// }
priority_queue<F, vector<F>, greater<F>>pq;
pq.push({0, 1, -1});
//dp[v][c] = min koszt dotarcia do v z uzyciem ostatniej krawedzi c, z wymuszeniem jej zmiany pozniej na sciezce
//dist[v] = min koszt po prostu dotarcia do v
//stanow jest O(sum of deg v + n) = O(m + n) ?????
vector<int>dist(n+1, oo);
dist[1] = 0;
while ((int)pq.size()){
auto [d, v, c] = pq.top(); pq.pop();
if (c == -1){
if (dist[v] < d) continue;
//nie wymuszamy zmiany koloru poprzedniej krawedzi
for (auto [e, vt]: g[v]){
for (auto [x, p]: vt){
//a) nie zmieniamy koloru krawedzi v---x (czyli nie wymuszamy tez zadnej zmiany)
int cost1 = sum[v][e] - p;
if (dist[x] > d + cost1){
dist[x] = d+cost1;
pq.push({dist[x], x, -1});
}
//b) zmieniamy kolor krawedzi c, ale dalej nie wymuszamy zmiany
//dirichlet ---> zawsze istnieje kolor na jaki mozemy zmienic
int cost2 = p;
if (dist[x] > d + cost2){
dist[x] = d+cost2;
pq.push({dist[x], x, -1});
}
//c) zmieniamy kolor krawedzi c, z wymuszeniem zmiany na pozniej dla nastepnej krawedzi na sciezce
int cost3 = 0;
if (dp[x][e] > d){
dp[x][e] = d;
pq.push({d, x, e});
}
}
}
} else {
if (dp[v][c] < d) continue;
//wymuszamy zmiane poprzedniej krawedzi c
for (auto [x, p]: g[v][c]){
int cost = sum[v][c] - p;
if (dist[x] > d + cost){
dist[x] = d+cost;
//nie oplaca sie zamieniac dwoch sasiednich krawedzi na optymalnej sciezce z koloru c na jakis inny kolor
//gdyby tak bylo, to moglibysmy usunac jedna zmiane i miec lepszy wynik
//wiec teraz nie wymuszamy zmiany koloru c
pq.push({dist[x], x, -1});
}
}
}
}
if (dist[n] == oo) cout << "-1\n";
else cout << dist[n] << "\n";
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
