#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 1e5 + 5;
struct node{
int a, b, c, p;
};
vector<node> edges[N];
vector<ar<int, 2>> ee[N];
int d[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
for(int i=0;i<m;i++){
node x; cin>>x.a>>x.b>>x.c>>x.p;
edges[x.a].push_back(x);
edges[x.b].push_back(x);
}
for(int i=1;i<=n;i++){
map<int, int> mm;
for(auto x : edges[i]){
mm[x.c] += x.p;
}
for(auto x : edges[i]){
int b = x.a + x.b - i;
if(mm[x.c] > x.p){
ee[b].push_back({i, min(x.p, mm[x.c] - x.p)});
} else {
ee[b].push_back({i, 0});
}
}
}
priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> q;
q.push({0, n});
memset(d, 127, sizeof d);
d[n] = 0;
while(!q.empty()){
int u = q.top()[1], D = q.top()[0]; q.pop();
if(D > d[u]) continue;
for(auto x : ee[u]){
if(d[x[0]] > d[u] + x[1]){
d[x[0]] = d[u] + x[1];
q.push({d[x[0]], x[0]});
}
}
}
if(d[1] > 1e18) cout<<-1<<"\n";
else cout<<d[1]<<"\n";
}
