#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int N = 1e5;
constexpr int M = 2e5;
vector<pair<int,int>> graf[N+9];
pair<int,int> kraw[M+9];
int kolor[M+9];
ll c[M+9];
map<pair<int,int>,ll> dst;
ll d(pair<int,int>a){
if (dst.find(a)==dst.end())return 1e17;
return dst[a];
}
ll suma[M+9];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,m;
cin >> n >> m;
for (int x=1;x<=m;x++){
cin >> kraw[x].first >> kraw[x].second >> kolor[x] >> c[x];
graf[kraw[x].first].push_back({kraw[x].second,x});
graf[kraw[x].second].push_back({kraw[x].first,x});
}
dst[{1,0}]=0;
priority_queue<pair<ll,pair<int,int>>> kol;
kol.push({0,{1,0}});
// + przejechalem zmieniajac kolory innych - zmienilem kolor tej
while(!kol.empty()){
auto ter=kol.top(); kol.pop();
if (-ter.first != d(ter.second)) continue;
int v,pop;
ll tajm;
v = ter.second.first; pop=ter.second.second;
if (v==11 && pop == -7){
pop++;
pop--;
}
tajm = -ter.first;
if (pop < 0)suma[kolor[-pop]]-=c[-pop];
else suma[kolor[pop]]=1e18;
for (auto x:graf[v]){
suma[kolor[x.second]] += c[x.second];
}
for (auto x:graf[v]){
ll op=tajm + c[x.second];
if (op < d({x.first,-x.second})){
dst[{x.first,-x.second}]=op;
kol.push({-op,{x.first,-x.second}});
}
op = tajm + suma[kolor[x.second]]-c[x.second];
if (op < d({x.first,x.second})){
dst[{x.first,x.second}]=op;
kol.push({-op,{x.first,x.second}});
}
}
for (auto x:graf[v])suma[kolor[x.second]]=0;
}
ll best=1e17;
for (int x=1;x<=m;x++){
best = min(best,d({n,-x}));
best = min(best,d({n,x}));
}
if (best > (ll)1e16) cout << "-1\n";
else cout << best << '\n';
}
