Esentiale

„L'essentiel est invisible pour les yeux.”

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 acelaș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ță

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$, $c$, cu semnificația că între nodurile $x$ și $y$ există o muchie având costul $c$.

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 \leq N \leq 10^3$
• $N \leq M \leq 10^5$
• $1 \leq c \leq 10^7$, pentru orice muchie din $G$
• Între oricare două noduri există cel mult o muchie.

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)$.