#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 10;
const ll INF = 1e18;
int c[MAXN];
ll p[MAXN], sum[MAXN];
map<pair<int, int>, int> marc;
map<pair<int, int>, ll> dist;
// dist[{v, 0}] = cheguei no v sem mudar suas arestas
// dist[{v, c}] = cheguei no v mudando uma aresta com a cor c
// e sou obrigada a usar a proxima aresta c tbm, pq to subtraindo
vector<pair<int, int>> adj[MAXN];
int n;
void dijkstra(int s){
priority_queue<pair<ll, pair<int, int>>> pq;
dist[{s, 0}] = 0;
pq.push({0, {s, 0}});
while(!pq.empty()){
auto [v, t] = pq.top().second;
pq.pop();
if(marc[{v, t}]) continue;
marc[{v, t}] = 1;
for(auto [u, i] : adj[v]) sum[c[i]] = 0;
for(auto [u, i] : adj[v]) sum[c[i]] += p[i];
for(auto [u, i] : adj[v]){
if(t != 0 && c[i] != t) continue;
// duas possibilidades:
// posso ir mudando (1) ou nao (2)
ll cost = sum[c[i]] - p[i];
if(t == 0){
// (1):
if(!dist.count({u, c[i]}) || dist[{v, t}] < dist[{u, c[i]}]){
dist[{u, c[i]}] = dist[{v, t}];
pq.push({-dist[{u, c[i]}], {u, c[i]}});
}
// (2):
cost = min(cost, p[i]);
}
// (2):
if(!dist.count({u, 0}) || dist[{v, t}] + cost < dist[{u, 0}]){
dist[{u, 0}] = dist[{v, t}] + cost;
pq.push({-dist[{u, 0}], {u, 0}});
}
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int m; cin >> n >> m;
for(int i=1; i<=m; i++){
int a, b; cin >> a >> b;
cin >> c[i] >> p[i];
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
dijkstra(1);
cout << (dist.count({n, 0}) ? dist[{n, 0}] : -1) << "\n";
return 0;
}
