Diferențe pentru problema/meta între reviziile #5 si #9

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

Elevii din Vianu înțeleg atât de bine algoritmii pentru găsirea arborelui parțial de cost minim, încât îi pot implementa și cu ochii închiși. De aceea, profesorul le-a dat o problemă ceva mai grea: găsirea celui de-al doilea arbore parțial în ordinea costului.

Elevii de la cercul de informatică înțeleg atât de bine algoritmii pentru găsirea arborelui parțial de cost minim, încât îi pot implementa și cu ochii închiși. De aceea, profesorul le-a dat o problemă ceva mai grea: găsirea celui de-al doilea arbore parțial în ordinea costului.

Se dă un graf neorientat cu $N$ noduri și $M$ muchii. Fiecare muchie are un cost pozitiv asociat și toate muchiile au costuri diferite.
 
Ajutați-i pe elevii din Vianu să calculeze costul celui de-al doilea arbore parțial minim. Mai exact, se cere cel mai mic număr natural $K$ cu proprietățile:

Se dă un graf neorientat conex cu $N$ noduri și $M$ muchii. Fiecare muchie are un cost pozitiv asociat și toate muchiile au costuri diferite. Ajutați-i pe elevii de la cerc să calculeze costul celui de-al doilea arbore parțial minim. Mai exact, se cere cel mai mic număr natural $K$ cu proprietățile:

# Există un arbore parțial de cost total [$K$].
# $K$ este strict mai mare decât costul arborelui parțial de cost minim pentru graful dat.
h2. Date de intrare

Fișierul de intrare $meta.in$ conține pe prima linie numerele $N$ și [$M$], despărțite printr-un spațiu. Pe următoarele $M$ linii se găsește câte o pereche de numere $x y$ cu semnificația că între nodurile $x$ și $y$ există o muchie.

Fișierul de intrare $meta.in$ conține pe prima linie numerele $N$ și [$M$], despărțite printr-un spațiu. Pe următoarele $M$ linii se găsește câte o pereche de numere $x y c$ cu semnificația că între nodurile $x$ și $y$ există o muchie de cost [$c$].

h2. Date de ieșire

* $1 ≤ N ≤ 1.000$
* $1 ≤ M ≤ 300.000$

* $M ≥ N$

* Nodurile sunt numerotate de la 1 la [$N$].

* Costurile muchiilor sunt numere naturale distincte cuprinse între 1 și 1.000.000$.

* Costurile muchiilor sunt numere naturale distincte cuprinse între 1 și 1.000.000.

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

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

| 5 6
1 2 1
2 4 5
4 3 2
3 1 7
3 5 4
4 5 9
| 14

|
h3. Explicație

...

Arborele parțial de cost minim are cost 12 și este format din muchiile (1, 2), (2, 4), (4, 3), (3, 5). Al doilea arbore în ordinea costului are costul 14 și este format din muchiile (1, 2), (1, 3), (3, 4), (3, 5).

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