#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const ll inf = 1e18;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m; cin>>n>>m;
vector<arr3> g[n + 1];
map<int, ll> mp[n + 1];
for (int tt = 1; tt <= m; tt++){
int x, y, c, w; cin>>x>>y>>c>>w;
g[x].pb({y, c, w});
g[y].pb({x, c, w});
mp[x][c] += w; mp[y][c] += w;
}
vector<vector<pil>> G = {{}};
map<pii, int> nd;
int cc = 0;
auto nw = [&](int x, int y){
if (nd.find({x, y}) == nd.end()){
nd[{x, y}] = ++cc;
G.pb({});
}
};
set<pii> st[m + 1];
for (int i = 1; i <= n; i++){
nw(i, 0);
for (auto [u, c, w]: g[i]){
nw(u, i);
G[nd[{i, 0}]].pb({nd[{u, i}], w});
nw(u, 0);
G[nd[{i, 0}]].pb({nd[{u, 0}], mp[i][c] - w});
}
for (auto [u, c, w]: g[i]){
st[c].insert({w, u});
}
for (auto [u, c, w]: g[i]){
nw(i, u);
G[nd[{i, u}]].pb({nd[{i, 0}], 0});
st[c].erase({w, u});
if (!st[c].empty()){
auto [W, T] = *prev(st[c].end());
G[nd[{i, u}]].pb({nd[{T, 0}], mp[i][c] - w - W});
}
st[c].insert({w, u});
}
for (auto [u, c, w]: g[i]){
st[c].clear();
}
}
priority_queue<pli, vector<pli>, greater<pli>> pq;
pq.push({0, 1});
vector<ll> dist(cc + 1, inf); dist[1] = 0;
while (!pq.empty()){
auto [d, v] = pq.top(); pq.pop();
if (d != dist[v]) continue;
for (auto [u, w]: G[v]){
ll f = d + w;
if (f < dist[u]){
dist[u] = f;
pq.push({f, u});
}
}
}
ll out = inf;
for (auto [p, y]: nd){
if (p.ff == n){
out = min(out, dist[y]);
}
}
cout<<((out == inf) ? -1 : out)<<"\n";
}
