#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
void solve(){
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n); // { adj_node, cost }
vector<multiset<int>> deg_col(n);
vector<vector<int>> edges(m); // {x, y, wt, col}
for(int i = 0; i < m; i++){
int x, y, col, wt;
cin >> x >> y >> col >> wt;
x--, y--;
deg_col[x].insert(col);
deg_col[y].insert(col);
edges[i] = {x, y, wt, col};
}
for(auto edge : edges){
int x = edge[0], y = edge[1], wt = edge[2], col = edge[3];
if(deg_col[x].count(col) == 1) adj[x].push_back({y, 0});
else adj[x].push_back({y, wt});
if(deg_col[y].count(col) == 1) adj[y].push_back({x, 0});
else adj[y].push_back({x, wt});
}
vector<int> dist(n, inf);
vector<int> processed(n, false);
dist[0] = 0;
priority_queue<pair<int, int>> q;
q.push({0, 0});
while(!q.empty()){
int a = q.top().second;
q.pop();
if(processed[a]) continue;
processed[a] = true;
for(auto [b, wt] : adj[a]){
if(dist[a] + wt < dist[b]){
dist[b] = dist[a] + wt;
q.push({-dist[b], b});
}
}
}
if(dist[n - 1] == inf){
cout << -1 << endl;
return;
}
cout << dist[n - 1] << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t--) solve();
return 0;
}
