#include<bits/stdc++.h>
#define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 1e5+5;
const int INF = 1e17;
vector<pair<int,int>> E[N];
struct Infor {
int u, v, c, w;
};
Infor adj[2*N];
int D[N];
map<int,int> color[N];
int n, m;
void Dijkstra() {
fill(D, D+n+1, INF);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, 1});
D[1] = 0;
while(!pq.empty()) {
auto p = pq.top(); pq.pop();
int d = p.first;
int u = p.second;
if(d > D[u]) continue;
for(pair<int,int> tmp: E[u]) {
int v = tmp.first;
int w = tmp.second;
if(D[v] > D[u] + w) {
D[v] = D[u] + w;
pq.push({D[v], v});
}
}
}
}
void solve() {
cin >> n >> m;
for(int i=1; i<=m; i++) {
int u, v, c, p; cin >> u >> v >> c >> p;
adj[i] = {u, v, c, p};
color[u][c]++;
color[v][c]++;
}
for(int i=1; i<=m; i++) {
int u = adj[i].u;
int v = adj[i].v;
int c = adj[i].c;
int w = adj[i].w;
if(color[u][c] > 1) E[u].push_back({v, w});
else E[u].push_back({v, 0});
if(color[v][c] > 1) E[u].push_back({u, w});
else E[v].push_back({u, 0});
}
Dijkstra();
cout << (D[n] == INF ? -1: D[n]) <<'\n';
}
signed main() {
if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--) solve();
}
