== include(page="template/taskheader" task_id="karb") ==

Se dă un graf neorientat conex cu $N$ noduri şi $M$ muchii. Muchiile au costul $0$ sau $1$. Se cere să se determine un arbore de acoperire de cost exact $K$.

Se dă un graf neorientat simplu conex cu $N$ noduri şi $M$ muchii. Muchiile au costul $0$ sau $1$. Se cere să se determine un arbore de acoperire de cost exact $K$.

h2. Date de intrare

Fişierul de intrare $karb.in$ conţine pe prima lini valorile lui $N$, respectiv $M$. Pe următoarele $M$ linii se vor afla câte trei numere $x y w$, separate printr-un spaţiu, reprezentând muchia $(x, y)$ de cost $w$.

Fişierul de intrare $karb.in$ conţine pe prima lini valorile lui $N$, $M$, respectiv $K$. Pe următoarele $M$ linii se vor afla câte trei numere $x y w$, separate printr-un spaţiu, reprezentând muchia $(x, y)$ de cost $w$.

h2. Date de ieşire

h2. Exemplu
table(example). |_. karb.in |_. karb.out |

| 6 8

| 6 8 3

1 3 1
1 2 0
2 3 1

4 2
|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="karb") ==

4539