URI Online Judge | 3119

As Aventuras do Calango Atômico

Por Vinicius Coelho BR Brazil

Timelimit: 5

Calango Atômico é um famoso personagem dos video-games da Studios Abertos de Programação (SAP). Ele teve sua namorada, Calanguete, raptada pelo maluco Dr. Lampinildo, aprisionando-a em seu castelo. Para resgatá-la, Calango precisa passar por uma série de fases contendo diversos obstáculos. Cada obstáculo tem um nível de dificuldade D imposto a ele. A medida que Calango avança uma fase, ele pode encontrar ramificações (ou furcações) que levam a outros cenários, cada um contendo um diferente obstáculo.

Calango está desesperado, pois o tempo necessário para concluir um obstáculo é equivalente ao seu nível de dificuldade. Por isso, ele deseja passar pela menor quantidade possível de obstáculos difíceis. Dado um número F de fases, cada uma contendo sua descrição, seu dever é calcular o menor tempo necessário para resgatar Calanguete.

Entrada

A primeira linha dos casos de teste consiste de um inteiro F (1 <= F <= 100), representando a quantidade de fases. Para cada uma das F fases, é fornecido dois inteiros C (2 <= C <= 104) e T (1 <= T <= 105), indicando a quantidade de cenários e a quantidade de transições de cenário, respectivamente. Cada uma das próximas T linhas indica que existe uma transição do cenário A para o cenário B com dificuldade D (1 <= D <= 106). Cada fase começa começa no cenário 1 e termina no cenário C.

Saída

A saída deve ser composta por um único inteiro contendo o menor tempo necessário para resgatar Calanguete, representado pelo soma dos tempos de cada fase.

Exemplo de Entrada Exemplo de Saída

1
11 13
1 2 5
2 3 7
2 4 4
2 9 23
3 5 11
4 6 7
5 7 1
5 9 2
6 8 8
7 10 6
8 9 2
9 10 3
10 11 9

37