我们先二分一个答案，对于每个答案，先加一级公路，如果不够k直接break，
然后再加二级公路，加的过程类似Kruskal。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
n, m, k :longint;
pre1, succ1, c1, c2 :array[..] of longint;
pre2, succ2 :array[..] of longint;
father :array[..] of longint;
ans :longint;
procedure swap(var a,b:longint);
var
c :longint;
begin
c:=a; a:=b; b:=c;
end;
procedure qs1(low,high:longint);
var
i, j, xx :longint;
begin
i:=low; j:=high;
xx:=c1[(i+j) div ];
while i<j do
begin
while c1[i]<xx do inc(i);
while c1[j]>xx do dec(j);
if i<=j then
begin
swap(pre1[i],pre1[j]);
swap(succ1[i],succ1[j]);
swap(c1[i],c1[j]);
inc(i); dec(j);
end;
end;
if i<high then qs1(i,high);
if j>low then qs1(low,j);
end;
procedure qs2(low,high:longint);
var
i, j, xx :longint;
begin
i:=low; j:=high;
xx:=c2[(i+j) div ];
while i<j do
begin
while c2[i]<xx do inc(i);
while c2[j]>xx do dec(j);
if i<=j then
begin
swap(pre2[i],pre2[j]);
swap(succ2[i],succ2[j]);
swap(c2[i],c2[j]);
inc(i); dec(j);
end;
end;
if i<high then qs2(i,high);
if j>low then qs2(low,j);
end;
procedure init;
var
i :longint;
begin
read(n,k,m);
for i:= to m- do
begin
read(pre1[i],succ1[i],c1[i],c2[i]);
pre2[i]:=pre1[i]; succ2[i]:=succ1[i];
end;
qs1(,m-);
qs2(,m-);
end;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
procedure main;
var
l, r, mid :longint;
i :longint;
fa, fb, a, b :longint;
cnt :longint;
begin
l:=; r:=;
while l<=r do
begin
mid:=(l+r) div ;
cnt:=;
for i:= to n do father[i]:=i;
for i:= to m- do
begin
if c1[i]>mid then break;
a:=pre1[i]; b:=succ1[i];
fa:=getfather(a); fb:=getfather(b);
if fa<>fb then
begin
father[fa]:=fb;
inc(cnt);
end;
end;
for i:= to m- do
begin
if (cnt<k) or (c2[i]>mid) then break;
a:=pre2[i]; b:=succ2[i];
fa:=getfather(a); fb:=getfather(b);
if fa<>fb then
begin
father[fa]:=fb;
inc(cnt);
end;
end;
if cnt<n- then l:=mid+ else
begin
ans:=mid;
r:=mid-;
end;
end;
writeln(ans);
end;
begin
init;
main;
end.