Problem H: Yu-kun Likes a Directed Graph

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらいお絵描きが大好きだ。 これまでゆう君は、丸と矢印で沢山絵を書いてきた。矢印は必ず丸と丸を結ぶようにして描いてある。ある日ゆう君はこれらの絵がグラフであることを知る。

丸は頂点と呼ばれ、矢印は辺と呼ばれているらしい。更にゆう君は、矢印を描く際に、必ずその上に１つ正の整数を書いていた。このように、辺に重みがあり有向な辺からなるグラフは重み付き有向グラフと呼ばれる。

今日ゆう君は、新たに閉路という言葉を知った。閉路とは、連結した辺の列であり、それに含まれるどの頂点も高々1度しか現れないもので、最初の頂点と最後の頂点が同じであるようなものをいう。閉路の辺の重みの総和が負になる場合、そのような閉路は負の閉路と呼ばれる。

新たな言葉を沢山知ったゆう君は一つの問題を思いついた。

Problem

閉路を持たない重み付き有向グラフが与えられる。 異なる２つの頂点 i, j を選び、i から j に重み w ( w < 0 ) の有向な辺を1本追加する。 これによってグラフ内に負の閉路ができるような i、 j をみつけ、その負の閉路に属する辺の重みの総和の最大値を求めよ。 そのような i, j が存在しない場合は"NA"と出力すること。

Input

V E w
s0 t0 c0
s1 t1 c1
...
s(E-1) t(E-1) c(E-1)

１行目に頂点の数 V, 辺の数 E, 追加する辺の重み w が空白区切りで与えられる。

続く E 行に有向な辺の情報が s_i t_i c_i として与えられる。 ( 0 ≤ i ≤ E-1 )

これは、 s_i から t_i に向けて重み c_i の有向な辺が存在することを表す。

Constraints

入力は以下の条件を満たす。

• 2 ≤ V ≤ 100000
• 1 ≤ E ≤ 500000
• -100 ≤ w < 0
• 0 ≤ c_i ≤ 100 ( 0 ≤ i ≤ E-1 )
• 0 ≤ s_i, t_i ≤ V-1 ( 0 ≤ i ≤ E-1 )
• 入力中に同じ s_i と t_i のペアが現れることはない
• s_i と t_i は異なる

Output

重み w の有向な辺を追加することで出来る負の閉路に属する辺の重みの総和の最大値を１行に出力せよ。 どこに辺を追加しても負の閉路が作れない場合は"NA"と出力すること。

Sample Input 1

3 2 -3
0 1 1
0 2 5

Sample Output 1

-2

Sample Input 2

3 2 -1
0 1 1
0 2 5

Sample Output 2

NA

Sample Input 3

7 8 -8
0 1 5
0 4 3
1 2 10
1 3 1
3 6 6
4 3 1
4 5 2
4 6 2

Sample Output 3

-1

Sample Input 4

5 4 -30
0 1 1
1 3 15
1 4 4
2 1 3

Sample Output 4

-12