#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
int n, m;
vector<array<int, 3>> adj[100100];
vector<pair<int, ll>> G[300300];
vector<pair<int, int>> P;
ll dist[300300];
int getidx(int x, int y){
return lower_bound(P.begin(), P.end(), pair<int, int>(x, y)) - P.begin() + n + 1;
}
void dijkstra(int s, int SZ){
fill(dist+1, dist+SZ+1, INF);
dist[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.emplace(0, s);
while(!pq.empty()){
auto [d, s] = pq.top(); pq.pop();
if (d > dist[s]) continue;
assert(d == dist[s]);
for (auto &[v, w]:G[s]) if (dist[v] > dist[s] + w){
dist[v] = dist[s] + w;
pq.emplace(dist[v], v);
}
}
}
int main(){
scanf("%d %d", &n, &m);
for (int i=1;i<=m;i++){
int x, y, z, w;
scanf("%d %d %d %d", &x, &y, &z, &w);
adj[x].push_back({y, z, w});
adj[y].push_back({x, z, w});
}
for (int i=1;i<=n;i++){
sort(adj[i].begin(), adj[i].end(), [&](const array<int, 3> &x, const array<int, 3> &y){
return x[1] < y[1];
});
for (auto &x:adj[i]) P.emplace_back(i, x[1]);
}
P.erase(unique(P.begin(), P.end()), P.end());
for (int i=1;i<=n;i++){
for (int j=0,r=0;j<(int)adj[i].size();j=r){
while(r<(int)adj[i].size() && adj[i][j][1]==adj[i][r][1]) ++r;
ll S = 0;
for (int k=j;k<r;k++) S += adj[i][k][2];
int i2 = getidx(i, adj[i][j][1]);
for (int k=j;k<r;k++){
auto [v, c, w] = adj[i][k];
G[i].emplace_back(v, min((ll)w, S - w));
G[i].emplace_back(getidx(v, c), 0);
G[i2].emplace_back(v, S - w);
}
}
}
dijkstra(1, n+P.size());
printf("%lld\n", dist[n]==INF?-1:dist[n]);
}
