#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,e;cin>>n>>e;
vector<tuple<int,int,int,int>> inpe;
vector<tuple<int,int,int,int,int>> ed={{0, 1, e,e, 0}};
vector<vector<int>> disc(n+1);
vector<vector<int>> m(n+1);
vector<vector<int>> al(n+1);
for(int i=0;i<e;i++){
int a,b,c,p;cin>>a>>b>>c>>p;
inpe.pb({a,b,c,p});
disc[a].pb(c);
disc[b].pb(c);
}
for(int i=1;i<=n;i++){
sort(disc[i].begin(),disc[i].end());
disc[i].erase(unique(disc[i].begin(),disc[i].end()),disc[i].end());
}
for(auto [a,b,c,p]:inpe){
al[a].pb(ed.size());
int inb=lower_bound(disc[b].begin(),disc[b].end(),c)-disc[b].begin();
int ina=lower_bound(disc[a].begin(),disc[a].end(),c)-disc[a].begin();
ed.pb({a, b, ina, inb, p});
al[b].pb(ed.size());
ed.pb({b, a, inb, ina, p});
m[a].resize(disc[a].size(),0);
m[b].resize(disc[b].size(),0);
m[a][ina]+=p;
m[b][inb]+=p;
}
int sz=ed.size();
for(int i=1;i<=n;i++){
ed.pb({0, i, e,e, 0});
}
//~ for(auto [a,b,c,d,p] : ed){
//~ cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<p<<endl;
//~ }
vector<int> dist(ed.size()+1, 1e15);
priority_queue<i5, vector<i5>, greater<i5>> pq;
pq.push({0, 1, e, 0, sz+1});
dist[sz+1]=0;
int ans=1e15;
while(!pq.empty()){
auto [cd, cur, fc, fp, edind] = pq.top(); pq.pop();
if(cur==n){
ans=min(ans, cd);
}
if(dist[edind] < cd) continue;
for(auto toi : al[cur]){
auto [_, to, curc, tc, tp] = ed[toi];
int cost;
// change edge colour.
cost=tp;
if(cd + cost < dist[toi]){
dist[toi]=cd+cost;
pq.push({dist[toi], to, disc[to][tc], tp, toi});
//~ printf("change edge col, at %lld cd %lld, fc %lld, going to %lld, cost is %lld\n"
//~ , cur, cd, fc, to, cost);
}
// dont change edge colour.
cost= max(0ll, m[cur][curc]-(disc[to][tc]==fc? fp : 0)-tp);
if(cd + cost < dist[sz+to]){
dist[sz+to]=cd+cost;
pq.push({dist[sz+to], to, e, 0, sz+to});
//~ printf("dont change, m[cur][%lld] is %lld, at %lld, cd %lld, fc %lld, going to %lld, cost is %lld\n",
//~ curc, m[cur][curc],cur, cd, fc, to, cost);
}
}
//~ for(int i=1;i<ed.size();i++){
//~ cout<<dist[i]<<" ";
//~ }
//~ cout<<endl;
}
if(ans >= 1e15){
cout<<-1;
}
else cout<<ans;
}
/*
6 6
1 2 1 1
2 3 1 1
2 4 1 1
3 5 1 1
4 5 1 1
5 6 1 1
6 6
4 3
1 2 1 3
2 3 1 4
3 4 1 3
1 4 2 6
4 5 3 5
5 6 3 5
*/
