Retallades P71496

El govern d’un país llunyà està retallant tot el que pot. Ara s’ha fixat que, sovint, per anar d’un poble a un altre hi ha més d’un camí possible (ja sigui una carretera directa, o una seqüència de carreteres que passa per altres pobles intermedis). Com que cada carretera té un cert cost de manteniment, el govern n’ha decidit eliminar per estalviar el màxim possible, tot mantenint el sistema de carreteres connex. Podeu calcular l’estalvi màxim?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de pobles (vèrtexs) n i el nombre de carreteres (arestes) m. Segueixen m triplets x y c, que indiquen que el cost de mantenir aquesta carretera entre x i y és c. Els pobles es numeren de 0 a n − 1. Suposeu 1 ≤ n ≤ 10⁴, n − 1 ≤ m ≤ 10 n, i 1 ≤ c ≤ 10⁴. Hi pot haver més d’una carretera entre dos pobles, i fins i tot carreteres amb x = y. Cada graf donat és connex.

Sortida

Per a cada cas, escriviu el màxim estalvi aconseguint que entre cada parell de pobles hi hagi exactament un camí.