#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define FOR(i , l , r) for(int i = (l) ; i <= (r) ; i++)
#define FOD(i , r , l) for(int i = (r) ; i >= (l) ; i--)
#define pii pair<int , int>
#define faster ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'
const int N = 2e5 + 5;
const int INF = 1e17;
int n , m;
struct nodes{
int v ; int c ; int p; int check;
};
vector<nodes> adj[N];
vector<pii> ad[N];
bool cmp(const nodes& x, const nodes& y) {
return x.c < y.c;
}
int dist[N];
void dijikstra(int s) {
FOR(i , 1 , n) dist[i] = INF;
dist[s] = 0;
priority_queue<pii , vector<pii> , greater<pii>> pq;
pq.push({0 , s});
while(pq.size()) {
int u = pq.top().se;
int cost = pq.top().fi;
pq.pop();
if(cost > dist[u]) continue;
for(auto v : ad[u]) {
if(dist[v.fi] > dist[u] + v.se) {
dist[v.fi] = dist[u] + v.se;
pq.push({dist[v.fi] , v.fi});
}
}
}
}
void solve () {
cin >> n >> m;
FOR(i , 1 , m) {
int a , b , c , p;
cin >> a >> b >> c >> p;
adj[a].push_back({b , c , p});
adj[b].push_back({a , c , p});
}
FOR(i , 1 , n) {
if(adj[i].size() == 0) continue;
sort(adj[i].begin() , adj[i].end() , cmp);
int cx = adj[i][0].c;
int cnt = 1;
FOR(j , 1 , adj[i].size() - 1) {
if(adj[i][j].c == cx) {
++cnt;
if(cnt >= 2) {
adj[i][j].check = 1;
adj[i][j - 1].check = 1;
}
}
else{
cx = adj[i][j].c;
cnt = 1;
}
}
FOR(j , 0 , adj[i].size() - 1) {
if(adj[i][j].check == 1) {
ad[i].push_back({adj[i][j].v , adj[i][j].p});
}
else{
ad[i].push_back({adj[i][j].v , 0});
}
}
}
dijikstra(1);
cout << (dist[n] != INF ? dist[n] : -1);
}
main () {
faster;
solve();
return 0;
}
