#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(){
int n,e;cin>>n>>e;
vector<tuple<int,int,int,int>> ed={{0, 1, 0, 0}};
vector<map<int,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;
al[a].pb(ed.size());
ed.pb({a, b, c, p});
al[b].pb(ed.size());
ed.pb({b, a, c, p});
m[a][c]+=p;
m[b][c]+=p;
}
int sz=ed.size();
for(int i=1;i<sz;i++){
auto [a,b,c,p] = ed[i];
ed.pb({0,b,0,0});
}
vector<int> dist(ed.size()+1, 1e15);
priority_queue<i5, vector<i5>, greater<i5>> pq;
pq.push({0, 1, 0, 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, tc, tp] = ed[toi];
int cost;
// change edge colour.
cost=tp;
if(cd + cost >= dist[toi])continue;
dist[toi]=cd+cost;
pq.push({dist[toi], to, tc, tp, toi});
//~ printf("change edge col, at %lld, fc %lld, going to %lld, cost is %lld\n", cur, fc, to, cost);
// dont change edge colour.
cost= max(0ll, m[cur][tc]-(tc==fc? fp : 0)-tp);
if(cd + cost >= dist[sz+to])continue;
dist[sz+to]=cd+cost;
pq.push({dist[sz+to], to, 0, 0, sz+to});
//~ printf("dont change, at %lld, fc %lld, going to %lld, cost is %lld\n", cur, fc, to, cost);
}
}
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
*/
