Ajude seu General

1164
Tempo Limite: 10 | Nível: 5

Descrição

Um bom general de guerra deve tomar decisões rápidas, e ao mesmo tempo ser um bom estrategista. Uma das funções do general é delegar soldados a diversos pontos estratégicos, de modo que o inimigo seja supreendido e derrotado. Há diversos pontos estratégicos no campo de batalha, assim como diversas rotas que interligam esses pontos.

O seu campo está, porém, sendo bombardeado, e essas rotas não são tão seguras mais. Uma vez que uma bomba caia em uma rota, tal terreno se torna irregular e a sua travessia se torna impossível. Para contornar tal problema, o general delegou uma nova tarefa a alguns soldados: encontrar novas rotas.

O general pediu sua ajuda então para calcular qual o caminho mais curto entre a base da operação e os pontos estratégicos. Você será informado sobre o estado inicial do campo de batalha, com N pontos estratégicos (sendo o ponto 1 a base da operação) e M rotas. Conforme as bombas inutilizam algumas rotas, e outras rotas vão sendo encontradas pelos soldados, você deve atualizar seu cálculo para que o general possa fazer bom uso de tais informações.

Boa sorte, o país depende de você.


Entrada

A entrada contém diversos casos de teste. Cada caso de teste inicia com dois inteiros, N e M (2 ≤ N ≤ 300 e 1 ≤ M ≤ 1000), representando, respectivamente, o número de pontos estratégicos e o número de rotas que interligam dois pontos estratégicos. Após, haverão M linhas, cada uma com três inteiros U, V e W (1 ≤ U, VN e 1 ≤ W ≤ 100) cada, representando que há uma rota que interliga o ponto U ao ponto V, em direção única, com distância W.

Haverá então um inteiro Q (1 ≤ Q ≤ 500), que representa o número de consultas ou atualizações que serão feitas sobre essas rotas. Nas próximas Q linhas haverá uma letra e um determinado número de inteiros.

Se a letra digitada for a letra R, haverá em seguida dois inteiros U e V (1 ≤ U, VN), indicando que a rota que antes interligava o ponto U até o ponto V foi bombardeada.

Caso a letra digitada for a letra I, haverá em seguida três inteiros U, V e W (1 ≤ U, VN e 1 ≤ W ≤ 100), indicando que foi encontrada uma nova rota que interliga o ponto U até o ponto V, com distância W.

E caso a letra digitada for a letra P, haverá em seguida um inteiro V (1 ≤ VN), e você deve informar ao general qual a distância mínima entre a base da operação e o ponto estratégico V.

A entrada termina quando N = M = 0.


Saída

Para cada caso de teste haverá um número não definido de linhas de saída. Sempre que, na entrada, o general requisitar a distância mínima entre a base da operação e um ponto estratégico (letra P), tal distância deve ser impressa em uma linha única. Caso não seja possível chegar a tal ponto estratégico, deve-se imprimir -1. Deve haver uma linha em branco após cada caso de teste.


Exemplos de Entrada Exemplos de Saída

3 3
1 2 2
2 3 3
1 3 4
5
P 3
R 2 3
P 3
I 2 3 1
P 3
0 0

4
4
3

Efetue Login ou Cadastre-se para submeter uma solução.



Criado por Cristhian Bonilha | Adaptado por erich.rodriguesf |