/**
* Solution by 1egend (polarity.sh)
* Date: 2024-11-13
* Contest: CSES Problemset - Graph Algorithms
* Problem: 1202
**/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ull unsigned long long
#define ll long long
const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;
void solve(){
int n, m; cin >> n >> m;
vector<ll> dist(n, 1e15);
map<pair<int, int>, vector<pair<int, int>>> multiple;
vector<vector<tuple<int, int, ll>>> adj(n);
for (int i = 0; i < m; i++){
int a, b, c; cin >> a >> b >> c;
--a; --b; --c;
ll d; cin >> d;
if (multiple[{a, c}].size() < 3){
multiple[{a, c}].pb({b, d});
}
if (multiple[{b, c}].size() < 3){
multiple[{b, c}].pb({a, d});
}
adj[a].pb({b, c, d});
adj[b].pb({a, c, d});
}
using T = tuple<ll, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
dist[0] = 0;
pq.push({0LL, 0, -1});
while(!pq.empty()){
auto [ndist, k, c] = pq.top();
pq.pop();
if (ndist != dist[k]) { continue; }
for (tuple<int, int, ll> &node: adj[k]){
int kk = get<0>(node);
int color = get<1>(node);
ll cost = get<2>(node);
if (multiple[{k, color}].size() == 1 || multiple[{k, color}].size() == 2 && c == color){
cost = 0;
}
if (ndist + cost < dist[kk]){
dist[kk] = ndist + cost;
pq.push({dist[kk], kk, color});
}
else if (multiple[{kk, color}].size() == 2){
int t = multiple[{kk, color}][0].first;
if (t == k){
t = multiple[{kk, color}][1].first;
}
if (ndist + get<2>(node) < dist[t]){
dist[t] = ndist + get<2>(node);
pq.push({dist[t], t, color});
}
}
}
}
cout << (dist[n - 1] == 1e15 ? -1: dist[n - 1])<< endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
