Problem
Se da un gráfico dirigido ponderado. Se requiere determinar si contiene un ciclo de peso negativo. Se garantiza que todos los vértices del gráfico son alcanzables desde el primero.
Entrada:
La primera línea del archivo de entrada contiene dos números naturales n y m — el número de vértices y aristas del gráfico respectivamente ( n ≤ 1 111, m ≤ 11 111).
Las siguientes m líneas contienen la descripción de los bordes, una por línea. El borde número i se describe mediante tres números bi, ei y wi — los números de los extremos de la costilla y su peso, respectivamente (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000) . Tenga en cuenta que el gráfico puede tener varios bordes y bucles.
Salida:
La primera línea del archivo de salida debe contener yes si el gráfico contiene un ciclo de peso negativo y no — de lo contrario.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| sí |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| no |