#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];
map<int, 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;
if(t == 0){
for(auto &x : adj[v]){
for(auto [u, i] : x.second){
ll cost = min(p[i], sum[v][c[i]] - p[i]);
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]}});
}
if(!dist[u].count(0) || d + cost < dist[u][0]){
dist[u][0] = d + cost;
pq.push({-dist[u][0], {u, 0}});
}
}
}
} else{
for(auto [u, i] : adj[v][t]){
ll cost = sum[v][t] - p[i];
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][c[i]].push_back({b, i});
adj[b][c[i]].push_back({a, i});
sum[a][c[i]] += p[i];
sum[b][c[i]] += p[i];
}
dijkstra(1);
cout << (dist[n].count(0) ? dist[n][0] : -1) << "\n";
return 0;
}
