Labirinto do Conhecimento
Problem
Atração "Labyrinth of Knowledge" foi construída na Summer Computer School (LCS). O labirinto consiste em N salas, numeradas de 1 a N, algumas das quais com portas entre elas. Quando uma pessoa passa por uma porta, o indicador de seu conhecimento muda em uma certa quantidade fixada para essa porta. A entrada do labirinto fica na sala 1, a saída – na sala N. Cada aluno passa pelo labirinto exatamente uma vez e entra em um ou outro grupo de estudo dependendo da quantidade de conhecimento adquirido (ao entrar no labirinto, esse indicador é zero). Sua tarefa é mostrar o melhor resultado.
Entrada:
A primeira linha da entrada contém inteiros N (1 <= N <= 2000) – número de quartos e M (1 <= M <= 10000) – Número de portas. Cada uma das próximas M linhas contém uma descrição da porta – os números das salas de onde leva e para as quais leva (você só pode passar pela porta em uma direção), bem como um número inteiro que é adicionado à quantidade de conhecimento ao passar pela porta (esse número não exceder 10000 no módulo). As portas podem levar de uma sala para ela mesma, pode haver mais de uma porta entre duas salas.
Saída:
Mostrar ":)" – se você pode obter uma quantidade ilimitada de conhecimento, ":(" – se o labirinto não pode ser passado e a quantidade máxima de conhecimento obtida de outra forma.
Exemplos
| # |
Entrada |
Saída |
| 1 |
2 2
1 2 3
1 2 7
|
7 |