#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n, m; cin >> n >> m;
vector<vector<vector<int>>> bad(n + 1);
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < m; i++){
int a;
vector<int> info(3);
//[0] = b
//[1] = color
//[2] = coste
cin >> a;
cin >> info[0] >> info[1] >> info[2];
bad[a].push_back(info);
swap(a, info[0]);
bad[a].push_back(info);
}
for (int i = 1; i <= n; i++){
map<int, int> val;
for (vector<int> u : bad[i]){
val[u[1]] += u[2];
}
int mn = 0;
if (val.size() == m){
for (int j = 1; j <= m; j++){
mn = min(mn, val[j]);
}
}
for (vector<int> u : bad[i]){
int best = min(mn + u[2], val[u[1]] - u[2]);
g[i].push_back({u[0], best});
}
}
/*for (int i = 1; i <= n; i++){
cout << "i::::::" << i << endl;
for (auto u : g[i]){
cout << u.first << ' ' << u.second << endl;
}
cout << endl;
}*/
vector<long long> dist(n + 1, 1e18);
priority_queue<pair<int, int>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
const auto [cdist, node] = pq.top();
pq.pop();
if (dist[node] != -cdist) continue;
for (auto x : g[node]){
if (x.second - cdist < dist[x.first]){
dist[x.first] = -(cdist - x.second);
pq.push({cdist - x.second, x.first});
}
}
}
if (dist[n] != 1e18) cout << dist[n] << endl;
else cout << -1 << endl;
}
