#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<int, ll> dist[MAXN], sum[MAXN];
map<int, bool> marc[MAXN];
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()){
ll d = -pq.top().first;
auto [v, t] = pq.top().second;
pq.pop();
if(marc[v][t]) continue;
marc[v][t] = true;
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[v][c[i]] - p[i];
if(t == 0){
// (1):
if(!dist[u].count(c[i]) || d < dist[u][c[i]]){
dist[u][c[i]] = d;
pq.push({-dist[u][c[i]], {u, c[i]}});
}
// (2):
cost = min(cost, p[i]);
}
// (2):
if(!dist[u].count(0) || d + cost < dist[u][0]){
dist[u][0] = d + 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);
cout << (dist[n].count(0) ? dist[n][0] : -1) << "\n";
return 0;
}
