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