#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Arc {
int nex, cost, nb, col, skip = -1;
};
struct Sit {
int i, dist;
bool operator <(const Sit& other) const {
return dist > other.dist;
}
};
const int N = 2e5 + 42, INF = 1e18;
vector<Arc> arc;
int n, m, dist[N];
vector<int> adj[N];
map<int, int> occ[N];
int Dijkstra() {
for(int i = 1; i < N; i++)
dist[i] = INF;
priority_queue<Sit> pq;
pq.push({0, 0});
while(!pq.empty()) {
Sit sit = pq.top();
pq.pop();
int i = sit.i, d = sit.dist;
if(d == dist[i]) {
for(int j : adj[i]) {
int dist2 = d;
if(arc[j].nb > 1)
dist2 += arc[j].cost;
if(dist2 < dist[arc[j].nex]) {
dist[arc[j].nex] = dist2;
pq.push({arc[j].nex, dist2});
}
if(arc[j].skip != -1) {
dist2 = d + arc[j].cost;
if(dist2 < dist[arc[j].skip]) {
dist[arc[j].skip] = dist2;
pq.push({arc[j].skip, dist2});
}
}
}
}
}
if(dist[n-1] != INF)
return dist[n-1];
return -1;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int a, b, col, cost;
cin >> a >> b >> col >> cost;
a--, b--;
occ[a][col]++;
occ[b][col]++;
adj[a].push_back(2*i);
adj[b].push_back(2*i+1);
arc.push_back({b, cost, 0, col});
arc.push_back({a, cost, 0, col});
}
for(int i = 0; i < n; i++)
for(int j : adj[i])
arc[j].nb = occ[i][arc[j].col];
for(int i = 0; i < n; i++) {
map<int, int> first;
for(int j : adj[i]) {
if(first.find(arc[j].col) == first.end())
first[arc[j].col] = j;
else if(arc[j].nb == 2) {
arc[j ^ 1].skip = arc[first[arc[j].col]].nex;
arc[first[arc[j].col] ^ 1].skip = arc[j].nex;
}
}
}
cout << Dijkstra();
}
