不难想到从小到大穷举a，判断在携带不超过a个B型精灵的情况下最少携带多少个B型精灵
这是一个经典的问题，显然要求出最小生成树，树上1到N路径上最大的边即是答案
所以我们要动态维护一个最小生成树可以用link cut tree维护
根据最小生成树的回路性质，我们加入一条边(u,v)，保留树上u-v路径上最大边和新边中小的那个
由于这里维护的是边权，我们可以把每条边当做一个点p(u,v)，连接(u,v)时，即是连接(u,p)和（v,p)
然后记录下路径上最大点权的编号即可
var son:array[..,..] of longint;
q,f,w,fa,v:array[..] of longint;
rev:array[..] of boolean;
s,e,a,b:array[..] of longint;
ans,i,n,m:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function getf(x:longint):longint;
begin
if f[x]<>x then f[x]:=getf(f[x]);
exit(f[x]);
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function root(x:longint):boolean;
begin
exit((son[fa[x],]<>x) and (son[fa[x],]<>x));
end; procedure update(x:longint);
begin
w[x]:=x;
if v[w[son[x,]]]>v[w[x]] then w[x]:=w[son[x,]];
if v[w[son[x,]]]>v[w[x]] then w[x]:=w[son[x,]];
end; procedure push(x:longint);
begin
if rev[x] then
begin
rev[son[x,]]:=not rev[son[x,]];
rev[son[x,]]:=not rev[son[x,]];
swap(son[x,],son[x,]);
rev[x]:=false;
end;
end; procedure rotate(x,w:longint);
var y:longint;
begin
y:=fa[x];
if not root(y) then
begin
if son[fa[y],]=y then son[fa[y],]:=x
else son[fa[y],]:=x;
end;
fa[x]:=fa[y];
son[y,-w]:=son[x,w];
if son[x,w]<> then fa[son[x,w]]:=y;
son[x,w]:=y;
fa[y]:=x;
update(y);
end; procedure splay(x:longint);
var y,t,i:longint;
begin
t:=;
i:=x;
while not root(i) do
begin
inc(t);
q[t]:=i;
i:=fa[i];
end;
inc(t);
q[t]:=i;
for i:=t downto do
push(q[i]);
while not root(x) do
begin
y:=fa[x];
if root(y) then
begin
if son[y,]=x then rotate(x,)
else rotate(x,);
end
else begin
if son[fa[y],]=y then
begin
if son[y,]=x then rotate(y,)
else rotate(x,);
rotate(x,);
end
else begin
if son[y,]=x then rotate(x,)
else rotate(y,);
rotate(x,);
end;
end;
end;
update(x);
end; procedure access(x:longint);
var y:longint;
begin
y:=;
repeat
splay(x);
son[x,]:=y;
update(x);
y:=x;
x:=fa[x];
until x=;
end; procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
swap(s[i],s[j]);
swap(e[i],e[j]);
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; procedure makeroot(x:longint);
begin
access(x);
splay(x);
rev[x]:=not rev[x];
end; procedure path(x,y:longint);
begin
makeroot(x);
access(y);
splay(y);
end; procedure link(x,y:longint);
begin
makeroot(x);
fa[x]:=y;
end; procedure cut(x,y:longint);
begin
makeroot(x);
access(y);
splay(y);
son[y,]:=;
fa[x]:=;
end; procedure deal(i:longint);
var x,y,z:longint;
begin
x:=getf(s[i]);
y:=getf(e[i]);
if x<>y then
begin
f[x]:=y;
link(s[i],n+i);
link(e[i],n+i);
end
else begin
x:=s[i];
y:=e[i];
path(x,y);
z:=w[y];
if v[z]>b[i] then
begin
cut(s[z-n],z);
cut(e[z-n],z);
link(s[i],n+i);
link(e[i],n+i);
end;
end;
end; begin
readln(n,m);
for i:= to m do
readln(s[i],e[i],a[i],b[i]);
for i:= to n do
f[i]:=i;
sort(,m);
for i:= to m do
begin
v[n+i]:=b[i];
w[n+i]:=n+i;
end;
ans:=;
i:=;
while i<m do
begin
inc(i);
deal(i);
while a[i]=a[i+] do
begin
inc(i);
deal(i);
end;
if getf()=getf(n) then
begin
path(,n);
ans:=min(ans,a[i]+v[w[n]]);
end;
end;
if ans= then writeln(-)
else writeln(ans);
end.