#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int c[200000];
int p[200000];
vector<pair<int, pair<int, int> > > adj[100000];
vector<ll> d;
bool visited[100000];
void dijkstra() {
d.assign(n, LONG_LONG_MAX);
priority_queue<pair<ll, int> > q;
d[0] = 0;
q.push(make_pair(0, 0));
while(!q.empty()) {
int v = q.top().second;
q.pop();
if(visited[v]) continue;
visited[v] = true;
set<int> s;
for(auto u : adj[v]) {
s.insert(u.second.first);
}
vector<int> v1;
vector<ll> v2;
vector<ll> v3;
while(!s.empty()) {
v1.push_back(*s.begin());
s.erase(*s.begin());
v2.push_back(0);
v3.push_back(2000000000000000);
}
for(auto u : adj[v]) {
int l = lower_bound(v1.begin(), v1.end(), u.second.first) - v1.begin();
v2[l] += (ll) u.second.second;
v3[l] = min(v3[l], d[u.first]);
}
for(auto u : adj[v]) {
if(visited[u.first]) continue;
int l = lower_bound(v1.begin(), v1.end(), u.second.first) - v1.begin();
d[u.first] = min(d[u.first], d[v] + ((ll) u.second.second));
d[u.first] = min(d[u.first], v3[l] + v2[l] - ((ll) u.second.second));
d[u.first] = min(d[u.first], d[v] + v2[l] - ((ll) u.second.second));
q.push(make_pair(-d[u.first], u.first));
}
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
int a, b, color, cost;
cin >> a >> b >> color >> cost;
a--; b--;
adj[a].push_back(make_pair(b, make_pair(color, cost)));
adj[b].push_back(make_pair(a, make_pair(color, cost)));
}
dijkstra();
if(d[n-1] != LONG_LONG_MAX) cout << d[n-1] << endl;
else cout << -1 << endl;
}
