Encontre o Caminho Mais Curto 4

É-lhe fornecido um mapa formado por n cidades e m estradas bidirecionais que ligam essas cidades. Cada estrada tem um comprimento inteiro não negativo, indicado por . O teu objetivo é encontrar o caminho mais curto entre a cidade 1 e a cidade n.

Entrada

A primeira linha contém dois inteiros separados por espaço, n e m (), que representam o número de cidades e o número de estradas, respetivamente.

As próximas m linhas contêm cada uma três inteiros separados por espaço, , e , que representam uma estrada entre as cidades e com comprimento ().

Saída

Dois inteiros, k e l, separados por um espaço. Aqui, k representa o número de cidades no caminho mais curto e l representa o comprimento desse caminho.

Na linha seguinte, imprime k inteiros separados por espaço, representando as cidades que compõem o caminho mais curto.

No caso de existirem vários caminhos mais curtos, podes apresentar qualquer um deles. Repara também que não é necessário minimizar o valor de k.

Exemplos