Fișierul intrare/ieșire	zapada.in, zapada.out	Sursă	Pregătire clasele 11-12
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.17 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Zapada (clasele 11 și 12)

Narnia este formată din N castele numerotate de la 1 la N, legate între ele prin M străzi cu dublu sens. În Narnia, iarna nu-i ca vara și de aceea ninge. Primarul știe cât costă deszăpezirea fiecărei străzi pe timp de un an. El dorește să afle costul minim C₀ pentru a deszăpezi un set de străzi care să permită circulația între oricare două castele. Ulterior, Primăria Narnia construiește câte o stradă nouă pe an, timp de K ani. Primarul dorește să recalculeze costul minim C_i al întreținerii rețelei de străzi în fiecare an (i = 1, 2, ..., K).

Date de intrare

Fișierul de intrare zapada.in conține

• pe prima linie numerele N, M și K, separate prin spații;
• pe următoarele M linii tripleți x y c cu semnificația „între castelele x și y există un drum care poate fi deszăpezit cu costul c”;
• pe ultimele K linii tripleți x_i y_i c_i cu semnificația „în al i_-lea an se construiește un drum între castelele _x_i și y_i care poate fi deszăpezit cu costul c_i”.

Date de ieșire

În fișierul de ieșire zapada.out se vor tipări K + 1 linii conținând, în ordine, valorile C₀, C₁, ..., C_K.

Restricții

• 1 ≤ N ≤ 10.000
• 1 ≤ M ≤ 100.000
• 1 ≤ K ≤ 1.000
• 1 ≤ c, c_i ≤ 1.000
• Între oricare două castele există (sau se construiește) cel mult un drum.
• Se garantează că între oricare două castele există cel puțin un drum, direct sau indirect.

Exemplu

Explicație

...