#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const ll inf = 1e17;
int main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin>>n>>m;
vector<array<int, 3> > adj[N];
vector<ll> price[N];
for(int i = 0; i < m; i++){
int u, v, c, p;
cin>>u>>v>>c>>p;
array<int, 3> a1 = {v, c, p};
array<int, 3> a2 = {u, c, p};
adj[u].pb(a1);
adj[v].pb(a2);
}
vector<ll> sum(N*2), cnt(N*2);
vector<int> seen;
for(int i = 1; i <= n; i++){
price[i].resize(adj[i].size());
for(auto itr: adj[i]){
seen.pb(itr[1]);
sum[itr[1]] += itr[2];
cnt[itr[1]]++;
}
int ind = 0;
for(auto itr: adj[i]){
if(cnt[itr[1]] == 1) price[i][ind] = 0;
else price[i][ind] = sum[itr[1]] - itr[2];
ind++;
}
for(auto itr: seen){
sum[itr] = 0;
cnt[itr] = 0;
}
seen.clear();
}
map<int, int> vis[N];
priority_queue<pair<ll, array<int, 4> > > pq;
pq.push({0, {1, 0, 0, 0}});
ll ans = inf;
while(!pq.empty()){
ll cost = -pq.top().first;
int node = pq.top().second[0];
int pre = pq.top().second[1];
int prec = pq.top().second[2];
int prep = pq.top().second[3];
pq.pop();
if(vis[node][pre]) continue;
vis[node][pre] = 1;
if(node == n){
ans = cost;
break;
}
if(pre == 0){ // nothing changed
int ind = 0;
for(auto itr: adj[node]){
if(price[node][ind] > 0 && !vis[itr[0]][node]) pq.push({-(cost + itr[2]), {itr[0], node, itr[1], itr[2]}});
if(itr[2] > price[node][ind] && !vis[itr[0]][0]) pq.push({-(cost + price[node][ind]), {itr[0], 0, 0, 0}});
ind++;
}
}
else{ // pre node changed, (- p[pre] in the case you dont change edge[node][nxt])
int ind = 0;
for(auto itr: adj[node]){
if(price[node][ind] > 0 && !vis[itr[0]][node]) pq.push({-(cost + itr[2]), {itr[0], node, itr[1], itr[2]}});
if(itr[2] > price[node][ind] - (itr[1] == prec ? prep : 0) && !vis[itr[0]][0]) pq.push({-(cost + price[node][ind] - (itr[1] == prec ? prep : 0)), {itr[0], 0, 0, 0}});
ind++;
}
}
}
if(ans == inf) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
/*
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
*/
