O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto começa com uma linha contendo o número X de vértices do grafo. As próximas X linhas de cada conjunto contém as listas de adjacências do grafo. O primeiro número de cada uma das X linhas é um inteiro N tal que 1 <= N <= X. Depois seguem-se vários pares de inteiros. Cada par possui um vértice V adjacente ao vértice N e o peso da aresta (N,V). A lista de pares termina quando o primeiro termo desse par é 0(zero) (esse par não deve ser considerado). Queremos identificar a árvore de menor custo desse grafo.
O arquivo de entrada é terminado por um conjunto de dados começando com X = 0. Esse conjunto não deve ser processado. Considere que 0 <= X <= 100.

Para cada conjunto, você deve imprimir X + 2 linhas. Na primeira linha, imprima o número do conjunto de dado, como mostrado na saída exemplo. Na próxima linha, imprima o peso da árvore encontrada (soma dos pesos de todas as suas arestas). Nas próximas X linhas, imprima a nova lista de adjacências do grafo (árvore), sem os custos.
Note que podem existir várias respostas, dê preferencia ao caminho com vértices de menor índice; para tanto, basta direcionar o heap de forma que dê prioridade ao menor índice.
Uma linha em branco separa cada conjunto.

O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto começa com uma linha contendo o número X de vértices do grafo. As próximas X linhas de cada conjunto contém as listas de adjacências do grafo. O primeiro número de cada uma das X linhas é um inteiro N tal que 1 <= N <= X. Depois seguem-se vá pares de inteiros. Cada par possui um vértice V adjacente ao vértice N e o peso da aresta (N,V). A lista de pares termina quando o primeiro termo desse par é 0(zero) (esse par não deve ser considerado). Após as X linhas, segue uma linha contendo um inteiro K que é um vértice do grafo. Queremos identificar as arestas que compõem os caminhos mais curtos de K para cada um dos vértices do grafo.
O arquivo de entrada é terminado por um conjunto de dados começando com X = 0. Esse conjunto não deve ser processado. Considere que 0 <= X <= 100.

Para cada conjunto, voce deve imprimir X linhas. Na primeira linha, imprima o número do conjunto de dado, como mostrado na saída exemplo. Nas proximas x-1 linhas imprima um par K -> V: (onde V é um vértice do grafo), o custo do melhor caminho até V e os vértices que compõem o melhor caminho para V.
Note que podem existir várias respostas, dê preferencia ao caminho com vértices de menor índice; para tanto, basta direcionar o heap de forma que dê prioridade ao menor índice.
Uma linha em branco separa cada conjunto.