#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
#define M 200005
#define fi first
#define se second
#define oo 1e18
typedef pair<int, pair<int, int>> ii;
int n, m, d[N], ua[M], va[M], cla[M], pa[M];
vector<int> adj[N];
map<int, int> sum[N], d2[N];
map<int, vector<int>> dj[N];
void ditra(){
priority_queue<ii, vector<ii>, greater<ii>> q;
for (int i = 1; i <= n; i++) d[i] = oo;
d[1] = 0;
q.push({0, {1, 0}});
while (!q.empty()){
int du = q.top().fi;
int u = q.top().se.fi;
int typ = q.top().se.se;
q.pop();
if (typ){
if (d2[u][typ] != du) continue;
for (auto x : dj[u][typ]){
int v = va[x];
if (v == u) v = ua[x];
int dis = du + sum[u][typ] - pa[x];
if (d[v] > dis){
d[v] = dis;
q.push({d[v], {v, 0}});
}
}
continue;
}
if (d[u] != du) continue;
for (auto x : adj[u]){
int v = va[x];
if (v == u) v = ua[x];
int d1 = du + sum[u][cla[x]] - pa[x];
if (d1 < d[v]){
d[v] = d1;
q.push({d1, {v, 0}});
}
d1 = du + pa[x];
if (d1 < d[v]){
d[v] = d1;
q.push({d1, {v, 0}});
}
d1 = du;
if (d2[v].find(cla[x]) == d2[v].end() || d2[v][cla[x]] > d1){
d2[v][cla[x]] = d1;
q.push({d1, {v, cla[x]}});
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++){
int u, v, c, p;
cin >> u >> v >> c >> p;
ua[i] = u; va[i] = v; cla[i] = c; pa[i] = p;
adj[u].push_back(i);
adj[v].push_back(i);
dj[u][c].push_back(i);
dj[v][c].push_back(i);
sum[u][c] += p;
sum[v][c] += p;
}
ditra();
if (d[n] >= oo) cout << -1;
else cout << d[n];
return 0;
}
