Monica s-a angajat ca administrator de retea si nu e o
misiune prea usoara. Reteaua de calculatoare pe care o administreaza este
formata din N calculatoare (numerotate
de la 1 la N).
O conexiune directa in retea este un cablu care leaga doua calculatoare
distincte si asigura comunicarea bidirectionala intre cele doua calculatoare
conectate. In retea exista M conexiuni
directe. Evident, conexiunile directe existente asigura comunicarea in
retea (adica oricare doua calculatoare in retea pot comunica - direct
sau indirect, prin intermediul altor calculatoare).
Monica intentioneaza sa protejeze pe cat posibil cablurile de retea. In
primul rand ea va selecta doar o parte dintre cele M conexiuni directe astfel incat comunicarea in retea sa fie
in continuare asigurata de conexiunile selectate, iar suma lungimilor
cablurilor sa fie cat mai mica. Monica numeste aceste conexiuni selectate
conexiuni minimale.
Seful Monicai, Ionel i-a furnizat masca protectoare de lungime K metri. Monica poate taia bucati din masca protectoare astfel incat
sa protejeze cablurile care realizeaza conexiunile minimale (un cablu
va fi protejat integral - pe toata lungimea lui - sau deloc).
Numim operatia de alegere a unei submultimi de conexiuni
minimale si imbracarea lor in masca protectoare pe toata lungimea lor
"mascare". Doua "mascari" se considera distincte daca
difera prin consumul total de masca protectoare utilizata. Evident consumul
total al unei mascari nu poate depasi K (numarul de metri de masca disponibili).
Monica doreste ca sa selecteze conexiunile minimale astfel
incat numarul de mascari distincte sa fie maxim.
Cerinţă
Scrieti un program care sa determine suma lungimilor conexiunilor
minimale, precum si numarul maxim de mascari distincte ale acestora.
Date de intrare
Fisierul de intrare retea.in contine pe prima linie numerele naturale N, M si K,
avand semnificatia din enunt. Urmeaza apoi M linii, pe fiecare linie aflandu-se trei numere naturale a, b si c reprezentand
faptul ca exista o conexiune directa intre calculatoarele a si b,
lungimea cablului fiind c metri.
Date de ieşire
Fisierul de iesire retea.out va contine o singura linie pe care vor fi scrise doua numere naturale
separate prin spatiu. Primul numar reprezinta suma lungimilor conexiunilor
minimale selectate (minima posibil). Al doilea numar reprezinta numarul
maxim de mascari distincte ale conexiunilor minimale.
Restricţii
1 <= N <= 1000
1
<= M <= 20000
1
<= K <= 50000
1 <= a, b <= N, a != b
1 <= c <= 50000
Intre doua calculatoare pot exista mai multe
conexiuni directe.
Daca numai suma lungimilor conexiunilor minimale este calculata corect
se acorda 30% din punctajul pe test.
Exemple
retea.in
retea.out
Explicatie
4 4 5
1 2 1
2 3 1
3 4 1
3 4 3
3 4
Singura multime de conexiuni minimale pe care oputem alege este {1-2,
2-3, 3-4}, acesta avand suma lungimilor 3, cea mai mica posibila cu proprietatea
ca oricare doua calculatoare pot comunica. Pentru aceasta multime de conexiuni
minimale exista 4 mascari distincte, avand consumul total de masca protectoare
0, 1, 2, respectiv 3. De exemplu pentru mascare cu consumul 1 se poate imbraca in masca protectoare
oricare conexiune minimala selectata. Pentru consumul 2 se pot imbraca
in masca protectoare oricare doua conexiuni minimale selectate. Pentru
consumul 3 se vor imbraca in masca protectoare toate cele 3 conexiuni
minimale. Evident, pentru consumul 0 nu vom imbraca in masca protectoare
nici o conexiune.