#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Arc {
int nex, cost, nb, col;
};
struct Sit {
bool ch;
int iArc, 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 = 0; i < N; i++)
dist[i] = INF;
priority_queue<Sit> pq;
for(int i : adj[0])
if(arc[i].nb > 1) {
dist[i] = arc[i].cost;
pq.push({true, i, arc[i].cost});
} else {
dist[i] = 0;
pq.push({false, i, 0});
}
while(!pq.empty()) {
Sit sit = pq.top();
if(dist[sit.iArc] == sit.dist) {
pq.pop();
int act = arc[sit.iArc].nex;
if(act == n-1)
return dist[sit.iArc];
for(int j : adj[act]) {
int d = dist[sit.iArc], need = 1;
if(arc[j].col == arc[sit.iArc].col && sit.ch)
need = 2;
if(arc[j].nb > need)
d += arc[j].cost;
if(d < dist[j]) {
dist[j] = d;
pq.push({arc[j].nb > need, j, d});
}
}
}
}
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 < 2*m; i++)
arc[i].nb = occ[arc[i ^1].nex][arc[i].col];
cout << Dijkstra();
}
