#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ar = array<int, 3>;
const ll inf = (ll)1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<ar>> E(n + 1);
vector<vector<pair<int, long long>>> adj(n + 1);
for(int i = 0;i < m;i++){
int a, b, c, p;
cin >> a >> b >> c >> p;
E[a].push_back({b, c, p});
E[b].push_back({a, c, p});
adj[a].emplace_back(b, p);
adj[b].emplace_back(a, p);
}
for(int i = 1;i <= n;i++){
map<int, ll> S;
for(auto [node, col, price] : E[i]){
S[col] += price;
}
for(auto [node, col, price] : E[i]){
adj[i].emplace_back(node, S[col] - price);
}
}
auto Do = [&](int src, vector<long long> &d)->void{
fill(d.begin(), d.end(), inf);
vector<bool> in_Q(n + 1);
d[src] = 0;
priority_queue<pair<long long, int>> pq;
pq.push({0, src});
while(!pq.empty()){
auto [_, node] = pq.top();
pq.pop();
if(in_Q[node]) continue;
in_Q[node] = 1;
for(auto [to, cost] : adj[node]){
if(d[node] + cost < d[to]){
d[to] = d[node] + cost;
pq.push({-d[to], to});
}
}
}
};
vector<long long> D(n + 1);
Do(1, D);
cout << (D[n] == inf ? -1 : D[n]) << '\n';
return 0;
}
