#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];
map<pair<int, int>, int> marc;
map<pair<int, int>, ll> dist, sum;
// dist[{v, 0}] = cheguei no v sem mudar suas arestas
// dist[{v, u}] = cheguei no mudando a aresta p/ o u
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]){
// duas possibilidades:
// posso ir mudando a aresta i (1) ou nao (2)
// (1):
ll cost = p[i];
if(!dist.count({u, i}) || dist[{v, t}] + cost < dist[{u, i}]){
dist[{u, i}] = dist[{v, t}] + cost;
pq.push({-dist[{u, i}], {u, i}});
}
// (2):
cost = sum[{v, c[i]}] - p[i];
if(c[t] == c[i]) cost -= p[t];
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});
}
for(int i=1; i<=n; i++){
for(auto [j, k] : adj[i]){
sum[{i, c[k]}] += p[k];
}
}
dijkstra(1);
ll ans = INF;
for(int i=0; i<=m; i++){
if(dist.count({n, i})){
ans = min(ans, dist[{n, i}]);
}
}
cout << (ans == INF ? -1 : ans) << "\n";
return 0;
}
