Campus 311 X29776

Statement

Logo em seu primeiro dia de aula no curso de Computação, José, primo de João e Maria, ficou impressionado com o tempo que demorou até chegar à UFMA. Além da distância entre seu bairro e a universidade, José observou que há muitos semáforos na cidade que atrasam o fluxo do trânsito durante o percurso.

Sendo assim, ele desenhou todo o trajeto que faz de sua casa até a UFMA através de rotas e quantificou o tempo que gasta em cada uma das avenidas.

Como você está em períodos mais avançados que José, escreva um programa que ajude-o a encontrar o melhor percurso para chegar à UFMA no menor tempo.

Input

A primeira linha de cada caso de teste traz $P (< 50)$ , o número de pontos no mapa que José traçou. Cada uma das $P$ linhas seguintes inicia com um número $n$ , a quantidade de avenidas que saem do ponto $p$ . Em seguida, há $n$ pares de números $x$ e $y$ , representando um outro ponto $q$ do mapa e o tempo que gasta no ônibus entre os pontos $p$ e $q$ .

Por fim, temos dois números $A$ e $B$ , que são os pontos representados pela posição atual de José e da UFMA.

No trajeto em que José faz, todas as avenidas são de mão dupla.

A entrada se encerra com $P = 0$ .

Output

Para cada caso de teste, a saída deve obedecer o formato apresentado no exemplo:

Rota $'i'$ : chegada em $'j'$ minutos., onde $'i'$ representa o caso de teste e $'j'$ é o tempo mínimo em que José chegaria na UFMA, se o Campus 311 seguisse a melhor rota.

Public test cases

Input

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

2
1 2 5
1 1 6
1 2

7
4 2 5 3 13 4 8 5 18
2 3 7 6 14
1 6 6
2 3 5 5 9
3 6 2 7 9 4 6
1 7 2
0
1 7

0

Output

Rota 1: chegada em 8 minutos.
Rota 2: chegada em 5 minutos.
Rota 3: chegada em 20 minutos.

Information

Author
Language: English
Official solutions: C++
User solutions: C C++