#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
uint64_t key64(int u, int c){
return ( (uint64_t)u << 32 ) ^ (uint64_t)c;
}
struct EdgeIn { int v; int color; ll p; };
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#if defined(LOCAL)
freopen("robot1.inp","r",stdin);
freopen("robot1.out","w",stdout);
#endif
int n;
int m;
if(!(cin >> n >> m)) return 0;
vector<vector<EdgeIn>> adj(n+1);
// we'll store total_p_per_node_color
unordered_map<uint64_t, ll> total;
total.reserve(m*2*2 + 10);
total.max_load_factor(0.7f);
vector<tuple<int,int,ll>> edges;
edges.reserve(m);
for(int i=0;i<m;i++){
int a,b,c; ll p;
cin >> a >> b >> c >> p;
// undirected edge stored both sides
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
// accumulate total p for (node,color)
total[key64(a,c)] += p;
total[key64(b,c)] += p;
edges.emplace_back(a,b,p);
}
// build graph with computed costs
vector<vector<pair<int,ll>>> g(n+1);
for(int u=1; u<=n; ++u){
for(auto &e: adj[u]){
int v = e.v;
int color = e.color;
ll p = e.p;
ll tot = total[key64(u,color)]; // sum of p for color at node u
// safety: tot >= p must hold
ll cost = min(p, tot - p);
g[u].push_back({v, cost});
}
}
// Dijkstra
vector<ll> dist(n+1, INF);
dist[1] = 0;
using pli = pair<ll,int>;
priority_queue<pli, vector<pli>, greater<pli>> pq;
pq.push({0,1});
while(!pq.empty()){
auto [d,u] = pq.top(); pq.pop();
if(d != dist[u]) continue;
for(auto &ed : g[u]){
int v = ed.first;
ll w = ed.second;
if(d > INF - w) continue; // overflow guard
ll nd = d + w;
if(nd < dist[v]){
dist[v] = nd;
pq.push({nd, v});
}
}
}
if(dist[n] >= INF) cout << -1 << '\n';
else cout << dist[n] << '\n';
return 0;
}
