Complex turístic P28681

Un complex turístic consisteix en un conjunt d’$n$ illes connectades amb ponts bidireccionals, cadascun dels quals té un cert cost de manteniment. Se sap que es pot anar des de qualsevol illa fins a qualsevol altra travessant un o més ponts.

El propietari del complex turístic viu en una de les illes, i té aquestes prioritats:

• Per estar molt tranquil, vol que l’illa on viu estigui connectada només amb un pont amb les altres illes.

• Per estalviar diners, vol conservar exactament $n-1$ ponts de manera que el complex turístic segueixi estant connectat.

Digueu si és possible complir les dues restriccions alhora. Si ho és, calculeu el cost mínim de manteniment de la xarxa de ponts triats.

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb el nombre d’illes $n$ i el nombre de ponts $m$. Segueixen $m$ triplets $x$ $y$ $c$ indicant un pont entre $x$ i $y$ amb cost $c$, amb $x \ne y$ i $1 \le c \le 10^5$. Suposeu $2 \le n \le 10^4$, $n - 1 \le m \le 5n$, que les illes es numeren des de 0, que no hi ha ponts repetits, i que el propietari del complex viu a l’illa 0.

Sortida

Per a cada cas, si no es poden complir les dues restriccions, escriviu “no”. Altrament, escriviu el cost mínim dels ponts triats.

Observació

Al codi, incloeu una explicació breu del vostre algorisme.