#include <bits/stdc++.h>
using namespace std;
#define int long long
#define oo 1e18
#define N 100005
#define M 200005
#define fi first
#define se second
typedef pair<int, pair<int, pair<int, int>>> iii;
struct ii
{
int v, c, cst;
};
int n, d[N], m, cle[M], u[M], v[M], cl[M], cst[M];
vector<int> adj[N];
map<int, int> sum[N], d2[N];
map<int, vector<int>> adj2[N];
void ditra(){
for (int i = 1; i <= n; i++){
d[i] = oo;
}
priority_queue<iii, vector<iii>, greater<iii>> q;
d[1] = 0;
q.push({0, {1, {0, 0}}});
while (!q.empty()){
int du = q.top().fi;
int uu = q.top().se.fi;
int typ = q.top().se.se.se;
int laste = q.top().se.se.fi;
q.pop();
if (typ){
if (d2[uu][typ] != du) continue;
for (auto x : adj2[uu][typ]){
int vv = v[x];
if (vv == uu) vv = u[x];
int d3 = sum[uu][typ] - cst[x] + du;
if (d3 < d[vv]){
d[vv] = d3;
q.push({d3, {vv, {x, 0}}});
}
}
}
else {
if (d[uu] != du) continue;
for (auto x : adj[uu]){
int vv = v[x];
if (vv == uu) vv = u[x];
int cost = cst[x];
int clr = cl[x];
int d1 = du + sum[uu][clr] - cost;
if (d1 < d[vv]){
d[vv] = d1;
q.push({d1, {vv, {x, 0}}});
}
int d22 = du + cost;
if (d22 < d[vv]){
d[vv] = d22;
q.push({d22, {vv, {x, 0}}});
}
int d3 = du;
if (d2[vv].count(clr) == 0 || d3 < d2[vv][clr]){
d2[vv][clr] = d3;
q.push({d3, {vv, {x, clr}}});
}
}
}
}
}
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, cst;
cin >> u[i] >> v[i] >> cl[i] >> cst[i];
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
sum[u[i]][cl[i]] += cst[i];
sum[v[i]][cl[i]] += cst[i];
adj2[u[i]][cl[i]].push_back(i);
adj2[v[i]][cl[i]].push_back(i);
}
ditra();
int res = d[n];
if (res >= oo) cout << -1;
else cout << res;
}
