Labirinto della Conoscenza
Problem
L'attrazione "Labyrinth of Knowledge" è stata costruita presso la Summer Computer School (LCS). Il labirinto è composto da N stanze, numerate da 1 a N, alcune delle quali hanno delle porte tra di loro. Quando una persona attraversa una porta, l'indicatore della sua conoscenza cambia di una certa quantità fissata per questa porta. L'ingresso al labirinto è nella stanza 1, l'uscita – nella stanza N. Ogni studente attraversa il labirinto esattamente una volta ed entra in uno o in un altro gruppo di studio a seconda della quantità di conoscenza acquisita (quando si entra nel labirinto, questo indicatore è zero). Il tuo compito è mostrare il miglior risultato.
Inserimento:
La prima riga dell'input contiene numeri interi N (1 <= N <= 2000) – numero di stanze e M (1 <= M <= 10000) – Numero di porte. Ognuna delle righe M successive contiene una descrizione della porta – i numeri delle stanze da cui conduce e a cui conduce (si può attraversare la porta solo in una direzione), nonché un numero intero che si aggiunge alla quantità di conoscenza quando si varca la porta (questo numero non superare 10000 in modulo). Le porte possono condurre da una stanza a se stessa, ci possono essere più di una porta tra due stanze.
Risultato:
Mostra ":)" – se puoi ottenere una quantità illimitata di conoscenza, ":(" – se il labirinto non può essere superato, e la quantità massima di conoscenza acquisita altrimenti.
Esempi
| # |
Input |
Uscita |
| 1 |
2 2
1 2 3
1 2 7
|
7 |