#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<ll,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 2e5 + 5;
vector<ll> dist[mn], cmpColor[mn], sumWeight[mn];
vector<bool> vis[mn];
vector<vector<pii>> adj[mn];
ll color[mn], weight[mn];
int colorID (int u, int c) {
return lower_bound(all(cmpColor[u]), c) - cmpColor[u].begin() + 1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<pii> edge(m);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b >> color[i] >> weight[i];
cmpColor[a].push_back(color[i]);
cmpColor[b].push_back(color[i]);
edge[i] = {a, b};
}
for (int i = 1; i <= n; i++) {
sort(all(cmpColor[i])), filter(cmpColor[i]);
int sz = cmpColor[i].size() + 1;
adj[i] = vector<vector<pii>>(sz);
dist[i] = vector<ll>(sz, LLONG_MAX);
sumWeight[i] = vector<ll>(sz);
vis[i] = vector<bool>(sz);
}
for (int i = 0; i < m; i++) {
int a, b; tie(a, b) = edge[i];
adj[a][colorID(a, color[i])].emplace_back(b, i);
adj[b][colorID(b, color[i])].emplace_back(a, i);
sumWeight[a][colorID(a, color[i])] += weight[i];
sumWeight[b][colorID(b, color[i])] += weight[i];
}
priority_queue<tpl> pq;
pq.emplace(0, 1, 0), dist[1][0] = 0;
while (pq.size()) {
ll dst; int u, forced; tie(dst, u, forced) = pq.top(); pq.pop();
if (vis[u][forced]) continue;
vis[u][forced] = 1;
if (forced) {
int clr = cmpColor[u][forced - 1];
for (pii item : adj[u][forced]) {
int v, idx; tie(v, idx) = item;
ll curW = sumWeight[u][forced] - weight[idx];
if (dist[u][forced] + curW < dist[v][0]) {
dist[v][0] = dist[u][forced] + curW;
pq.emplace(-dist[v][0], v, 0);
}
}
}
else {
for (int clrID = 1; clrID < adj[u].size(); clrID++) {
int clr = cmpColor[u][clrID - 1];
for (pii item : adj[u][clrID]) {
int v, idx; tie(v, idx) = item;
int nxtForced = colorID(v, clr);
// use color[idx] for next node
ll curW = (v == n ? weight[idx] : 0);
if (dist[u][forced] + curW < dist[v][nxtForced]) {
dist[v][nxtForced] = dist[u][forced] + curW;
pq.emplace(-dist[v][nxtForced], v, nxtForced);
}
// use any color for next node
curW = min(weight[idx], sumWeight[u][clrID] - weight[idx]);
if (dist[u][forced] + curW < dist[v][0]) {
dist[v][0] = dist[u][forced] + curW;
pq.emplace(-dist[v][0], v, 0);
}
}
}
}
}
ll ans = *min_element(all(dist[n]));
cout << (ans == LLONG_MAX ? -1 : ans);
return 0;
}
