Semàfors P68618

Després d’una llarga partida a l’Age of Empires, els participants de la UPC decideixen anar a registrar-se per al SWERC abans que sigui massa tard. Per això han d’anar des de l’hotel fins a la universitat de Porto.

La ciutat té $n$ illes (numerades entre 0 i $n-1$) i $m$ passos de vianants. Cada pas de vianants és bidireccional, connecta dues illes diferents, i té un semàfor que està en verd o en vermell. Els semàfors canvien d’estat cada $t$ segons, tots a la vegada. Suposant negligible el temps de creuar els passos de vianants amb el semàfor en verd, i que no es creuarà mai en vermell, quant es triga en anar des de l’illa 0 (l’hotel) fins a l’illa $n-1$ (la universitat)?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$, $m$ i $t$. Segueixen $m$ triples $x$ $y$ $c$ indicant que hi ha un pas de vianants entre les illes $x$ i $y$, i que el semàfor corresponent inicialment està en verd si $c$ és 0, o en vermell si $c$ és 1. Assumiu $2 \le n \le 10^4$, $0 \le m \le 5n$, $1 \le t \le 50$, $x \ne y$, i que entre dues illes només hi haurà com a màxim un pas de vianants.

Sortida

Per a cada cas, escriviu el temps mínim d’anar des de 0 fins a $n-1$. Si no és possible anar des de 0 fins a $n-1$, escriviu “WOLOLO!!!”.