81. 負環判斷

你知道如果一張圖上有負環，求最短路徑會是超困難的問題嗎(NP-hard)，為了拯救大家避免遇到負環，你能預先檢查如果從 $0$ 號點出發是否會遇到負環嗎？

輸入

僅有單筆測資

第一行有兩個數字 $n$, $m$ 表示有 $n$ 個點 $m$ 條邊。

接下來有 $m$ 行，每行有三個數字 $i,j,v$ ，表示有一條 單向 邊 $i$ 到 $j$ 權重是 $v$

圖可能有 自環 跟 重邊 。

輸出

如果從$0$號點出發會經過負環，請輸出 GG ，否則輸出 PPAP。最後要換行

條件限制

對於所有測資：

• $1\leq n\leq 100$
• $0\leq i,j <n$
• $-100\leq v\leq $100

對於部分測資

• 20% $n\leq 10$
• 80% 沒有限制

範例輸入1

3 3
0 1 1000
1 2 15
2 1 -42

範例輸出1

GG

範例輸入2

4 4
0 1 10
1 2 20
2 3 30
3 0 -60

範例輸出2

PPAP

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 26