#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 201, M = 40001;
int n, m;
multiset<pair<int, int>> adj[N];
int c[M], d[M];
pair<int, int> edges[M];
vector<int> dijkstra(int source){
vector<int> dist(n + 1, 1e15);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, source});
dist[source] = 0;
while (!pq.empty()) {
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
for (auto &n : adj[u]){
if (dist[n.first] > d + c[n.second]){
dist[n.first] = d + c[n.second];
pq.push({dist[n.first], n.first});
}
}
}
return dist;
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
adj[i].clear();
}
for (int i = 0; i < m; ++i){
int u, v;
cin >> u >> v >> c[i] >> d[i];
adj[u].insert({v, i});
edges[i] = {u, v};
}
int ans = 1e15;
for (int i = 0; i < m; ++i) { // for each edge
for (int bin_val = 0; bin_val < 2; ++bin_val) { // binary value which is 0 or 1
if (bin_val) {
adj[edges[i].first].erase(adj[edges[i].first].find({edges[i].second, i}));
adj[edges[i].second].insert({edges[i].first, i});
}
vector<int> start = dijkstra(1); // from start
vector<int> target = dijkstra(n); // from target
int ans_temp = d[i] * bin_val + start[n] + target[1];
ans = min(ans, ans_temp);
if (bin_val) {
adj[edges[i].second].erase(adj[edges[i].second].find({edges[i].first, i}));
adj[edges[i].first].insert({edges[i].second, i});
}
}
}
if (ans == (int)(1e15)) {
cout << -1;
}
else{
cout << ans;
}
return 0;
}
