Xarxa de carreteres P64299

Un país té n ciutats i m carreteres bidireccionals, les quals permeten anar de qualsevol ciutat a qualsevol altra, ja sigui de forma directa o passant per ciutats intermèdies. Cada carretera té un cert cost de manteniment. A més, el govern considera que algunes de les carreteres són imprescindibles.

Per reduir costos, el govern vol escollir el subconjunt més barat de carreteres que inclogui totes les carreteres imprescindibles i amb el qual es pugui seguir anant de qualsevol ciutat a qualsevol altra ciutat. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguides d’m quàdruples x y c i, una per carretera, on x i y són les ciutats connectades directament (amb x ≠ y), c és el cost de manteniment de la carretera, i i és un càracter que és ‘I’ o ‘N’ depenent de si la carretera és imprescindible o no.

Suposeu 2 ≤ n ≤ 10⁴, n − 1 ≤ m ≤ 5n, que la xarxa de carreteres és connexa, que les ciutats es numeren entre 0 i n−1, que no hi ha més d’una carretera entre dues ciutats x i y, i que cada c està entre 0 i 10⁴.

Sortida

Per a cada cas, escriviu el mínim cost d’una xarxa de carreteres que compleixi les restriccions demanades.