Fie G un graf neorientat conex cu N noduri și M muchii. Nodurile sunt numerotate de la 1 la N iar muchiile au asociate costuri numere naturale date. Un graf parţial al lui G conex şi fără cicluri este denumit arbore parţial. Costul unui arbore parțial este suma costurilor muchiilor arborelui. Deoarece unele muchii pot avea aceelași cost, este posibil ca graful G să aibă mai mulți arbori parțiali de cost minim. Definim o muchie a grafului G ca fiind esențială dacă ea face parte din toți arborii parțiali de cost minim ai lui G.

Cerința

Scrieţi un program care, cunoscând graful, rezolvă următoarele două cerinţe:
1. determină costul unui arbore parțial de cost minim al lui G;
2. determină numărul de muchii esențiale ale grafului G.

Date de intrare

Fișierul de intrare esentiale.in conţine pe prima linie numerele naturale N, M și C, reprezentând numărul de noduri, numărul de muchii și numărul cerinței (1 sau 2). Următoarele M linii conțin câte trei numere: x y cost, cu semnificația că între nodurile x și y există o muchie având costul cost.

Date de ieșire

Fișierul de ieșire esentiale.out va conţine o singură linie pe care va fi scris răspunsul la cerinţa C.

Restricții și precizări

• 2 ≤ N ≤ 1000
• N ≤ M ≤ 100.000
• 1 ≤ cost ≤ 10.000.000, pentru orice muchie din G
• Între oricare două noduri există cel mult o muchie.
• Pentru 34 de puncte, C = 1
• Pentru 29 de puncte, C = 2 și M ≤ 1000
• Pentru 27 de puncte, C = 2 și M > 1000
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru testele din exemple

Exemplul 1:

esentiale.in

5 7 1
1 2 3
3 2 4
3 4 3
1 3 2
2 5 3
5 4 1
4 1 4

esentiale.out

9

Explicație

C = 1 deci se rezolvă doar prima cerință. Graful G este cel din desen și unul din arborii parțiali de cost minim ai lui este format din muchiile: (4, 5), (1, 3), (1, 2), (2, 5). Costul total minim este 9=1+2+3+3, egal cu suma costurilor muchiilor în ordinea specificată mai sus.

Exemplul 2:

esentiale.in

5 7 2
1 2 3
3 2 4
3 4 3
1 3 2
2 5 3
5 4 1
4 1 4

esentiale.out

2

Explicație

C = 2 deci avem de rezolvat cerința a doua, pentru același graf G. Există trei arbori parțiali de cost minim, formați din următoarele muchii:
(4, 5), (1, 3), (1, 2), (2, 5)
(4, 5), (1, 3), (1, 2), (3, 4)
(4, 5), (1, 3), (3, 4), (2, 5)
Doar două muchii sunt în toți arborii parțiali de cost minim și anume (4, 5) și (1, 3).