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 \ne 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 \le n \le 10^4$, $n - 1 \le m \le 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^4$.

Sortida

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