Campus 311 X29776

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.