浦島太郎

題目敘述

浦島太郎被帶到聾宮後，發現到處都是會讓他變老的機關，你可以幫幫他如何以最年輕的身體逃離聾宮嗎？聾宮是由$N$個房間所組成，有$M$條單向的道路連接這些房間，每條道路都設有機關，會改變浦島太郎的年齡；其中一個房間設有出口，可以離開聾宮。為了用最年幼的身體練習鐵沙掌，請問他離開聾宮時最少會老幾歲？ 注意：就算走到了有出口的房間，也可以選擇要不要離開。

輸入說明

第一行有兩個數字$N,M$表示有$N$個房間，$M$條連接房間的單向道路，房間的編號為$0,1,2,...,N-1$，編號0號是浦島太郎一開始所在的房間，編號$N-1$號的房間有出口。接下來有$M$行，每行有三個整數(int)$A,B,C$表示間有一條從$A$房間到$B$房間的單向道路，通過它的時候會變老$C$歲(小於零的值代表變年輕)。 其中 $0\leq A,B\leq N-1, |C| \leq 10^6$

輸出說明

如果有辦法變年輕超過$10^{10000}$歲，請輸出hug hug，如果沒有辦法走出聾宮，請輸出alone forever，否則請輸出離開聾宮時最少會變老幾歲(如果是變年輕，請輸出負的值)。

範例輸入1

4 6
0 1 1000
0 2 3
2 1 100
1 2 100
1 3 4
2 3 1000

範例輸出1

107

範例輸入2

5 5
0 1 1
1 2 -1
2 3 -1
3 1 -1
1 4 1

範例輸出2

hug hug

配分方法

• 30% $1 \leq N \leq 100$, $1 \leq M \leq 1000$
• 100% $1 \leq N \leq 1000$, $1 \leq M \leq 100000$

Hints

備註

Judge Setting