Fuga no Zoológico

Durante uma forte tempestade, diversos animais escaparam de seus recintos no famoso Zoológico de Nlogônia. Um grupo de tratadores precisa conduzir um dos animais mais perigosos — o leopardo — até um setor seguro do zoológico, sem pará-lo em hipótese alguma, pois ele pode ficar agressivo e atacar caso tenha que parar.

O percurso do zoológico é formado por várias encruzilhadas, todas solucionadas com rotatórias para facilitar o trânsito contínuo de veículos e evitar paradas. No entanto, entre cada rotatória, existe uma passagem com um portão automático de controle:

• Alguns portões abrem nos minutos múltiplos de $3$ e ficam fechados nos demais;
• Outros ficam fechados nos minutos múltiplos de $3$ e abrem nos outros minutos.

Todas as passagens têm sentido único e levam exatamente um minuto para serem atravessadas.

O transporte começará exatamente ao meio-dia em uma das rotatórias do zoológico e deve ser finalizado em outra rotatória específica, onde a equipe especializada estará aguardando para confinar o leopardo em segurança. Caso o carrinho dos tratadores seja forçado a parar em algum portão, o animal acabará se estressando e atacando.

Isso significa que o grupo pode até dar voltas eternamente, porém ficará sem combustível eventualmente e não conseguirá evitar o ataque.

Sua tarefa é determinar o menor tempo, em minutos, para conduzir o leopardo de maneira segura até o setor de saída, sem que nenhuma parada seja imposta por um portão fechado.

Entrada

A primeira linha da entrada contém quatro inteiros $N$, $E$, $S$, $M$, indicando, respectivamente:

• O número de rotatórias do zoológico (numeradas de $0$ a $N-1$),
• O número da rotatória de entrada onde o animal está localizado,
• O número da rotatória de saída,
• O número de passagens entre as rotatórias.

Cada uma das $M$ linhas seguintes contém três inteiros $A$, $B$ e $T$, representando:

• A rotatória de origem da passagem,
• A rotatória de destino,
• E a programação do portão: $T = 1$ se o portão abre nos minutos múltiplos de $3$, $T = 0$ se o portão fecha nos minutos múltiplos de $3$.

Saída

Imprima uma única linha contendo um único número inteiro: o menor tempo possível (em minutos) para conduzir o leopardo em segurança até a saída. Se não existe forma de realizar o trajeto sem que o animal pare e ataque, imprima uma única linha contendo apenas o caractere ‘*’.

Restrições

• $2 \leq N \leq 500$
• $1 \leq M \leq 2\ 000$
• $0 \leq E, S \leq N - 1$
• Pode haver até duas passagens de uma rotatória $A$ para outra $B$ (possivelmente igual a $A$). No caso de haver duas passagens, uma delas terá portão que abre nos minutos múltiplos de $3$ e a outra portão que fecha nesses instantes.

Exemplos

Exemplo de entrada 1

6 5 4 7
0 1 0
1 2 0
1 2 1
2 3 1
2 4 0
3 0 0
5 0 1

Exemplo de saída 1

8

Exemplo de entrada 2

4 0 3 4
0 1 1
1 2 0
2 3 1
2 0 0

Exemplo de saída 2

*