Sykli

• Time limit: 1.00 s
• Memory limit: 128 MB

Annettuna on suunnattu verkko, ja tehtäväsi on selvittää, onko verkossa negatiivista sykliä. Jos verkossa on negatiivinen sykli, sinun tulee vielä tulostaa sen solmut.

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $m$: solmujen määrä ja kaarten määrä. Solmut on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden kaaren. Rivillä on kolme kokonaislukua $a$, $b$ ja $c$. Tämä tarkoittaa, että solmusta $a$ solmuun $b$ on kaari, jonka pituus on $c$.

Voit olettaa, että jokainen kaari alkaa ja päättyy eri solmussa.

Tuloste

Jos verkossa on negatiivinen sykli, tulosta ensin "10-4" ja sitten toiselle riville syklin solmut järjestyksessä jostain solmusta alkaen. Jos verkossa on useita negatiivisia syklejä, voit tulostaa minkä tahansa niistä.

Jos verkossa ei ole negatiivista sykliä, tulosta vain "QAQ".

Rajat

• $1 \le n \le 2500$
  
• $1 \le m \le 5000$
  
• $1 \le a,b \le n$
  
• $-10^9 \le c \le 10^9$
  

Esimerkki

Syöte:
4 5
1 2 1
2 4 1
3 1 1
4 1 -3
4 3 -2

Tuloste:
10-4
1 2 4 1