SPOJ Brasil

Roberto trabalha no setor de compras de um grande laboratório de pesquisa privado com diversas filiais pelo mundo. Entre suas tarefas, ele deve comprar passagens aéreas para os pesquisadores e executivos em suas viagens a outras filiais ou a congressos e feiras. Essas viagens são sempre feitas de avião.

Encontrar a melhor forma de chegar a um destino não é uma tarefa simples, pois deve-se levar em conta os requisitos de cada cargo, o tempo de vôo e o custo da passagem para decidir-se qual é a melhor. Roberto possui uma tabela com todos os vôos disponíveis nas companhias aéreas. Todo vôo inicia na cidade de origem O e termina na cidade destino D e possui um custo C e um tempo de vôo T. Pode existir mais de um vôo entre um dado par de cidades, com preços e tempos distintos. O fato de existir um vôo da cidade O à cidade D não significa que existe um vôo da cidade D à cidade O.

Sempre que um funcionário de um dos laboratórios necessita viajar da cidade U à cidade V , Roberto deve comprar as passagens necessárias para que ele chegue em seu destino ou informar ao funcionário que não é possível realizar tal viagem utilizando somente o transporte aéreo. Além disso, Roberto deve seguir a seguinte política de aquisição de passagens:

• Se for um pesquisador, o custo da viagem deve ser o menor possível. Caso existam duas ou mais viagens com o mesmo custo, o tempo de viagem deve ser o menor possível. Em caso de novo empate, a quantidade de escalas (ou seja, a quantidade de cidades entre a origem e o destino) deve ser a menor possível.
• Se for um executivo, o tempo de viagem deve ser o menor possível. Caso existam duas ou mais viagens com o mesmo tempo, o custo deve ser o menor possível. Em caso de novo empate, a quantidade de escalas (ou seja, a quantidade de cidades entre a origem e o destino) deve ser a menor possível.

Você trabalha no departamento de informática desse mesmo laboratório e deve implementar um programa para auxiliar Roberto.

Tarefa

Escreva um programa que determine os valores de custo, tempo e escalas para realizar a viagem entre as duas cidades especificadas para um determinado funcionário respeitando as restrições descritas. Note que a origem e o destino não contam no cálculo de escalas.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém dois inteiros N e F (1 ≤ N ≤ 1.000, 1 ≤ F ≤ 1.000.000) indicando o número de cidades e o número de vôos e uma letra indicando o cargo do funcionário no laboratório (P para pesquisador e E para executivo). As cidades são numerada de 1 a N. A linha seguinte contém dois inteiros U e V indicando a cidade inicial e a cidade final da viagem (1 ≤ U ≤ N, 1 ≤ V ≤ N). As N linhas seguintes contêm 4 inteiros O, D, C e T representando as informações de cada trecho: cidade de origem, cidade destino, custo e tempo (1 ≤ O ≤ N, 1 ≤ D ≤ N, 1 ≤ C ≤ 10.000, 1 ≤ T ≤ 10.000).

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo três inteiros separados por espaço representando o custo, o tempo e o total de escalas para o funcionário realizar a viagem respeitando a política da empresa de aquisição de passagens, ou -1 caso não seja possível realizar a viagem.

Exemplo

Entrada:
5 6 P
1 3
1 2 10 7
2 3 5 8
1 4 4 5
4 5 4 5
5 3 7 5
1 2 15 12

Saída:
15 15 1

Entrada:
3 2 E
1 3
1 2 1 2
1 2 1 2

Saída:
-1

Entrada:
3 4 P
1 2
1 2 17 3
1 2 10 5
1 3 1 1
3 2 8 5

Saída:
9 6 1