Problem: Background

The kindergarten attached to the University of Aizu is a kindergarten where children who love programming gather. Yu, one of the kindergarten children, loves drawing as much as programming. So far, Yu-kun has drawn many pictures with circles and arrows. The arrows are always drawn to connect the circles. One day Yu finds out that these pictures are graphs.

It seems that circles are called vertices and arrows are called edges. Furthermore, when drawing an arrow, Yu always wrote one positive integer on it. A graph consisting of directed edges with weights in this way is called a weighted directed graph.

Today Yu-kun learned a new word, the cycle of the cycle. A cycle is a sequence of connected edges in which all vertices appear at most once, and the first and last vertices are the same. If the sum of the weights of the edges of a cycle is negative, then such a cycle is called a negative cycle.

Yu-kun, who knew a lot of new words, came up with a problem.

Problem

A weighted directed graph with no cycle is given. Select two different vertices i and j and add one directed edge with weight w (w <0) from i to j. Find i and j in the graph that create a negative cycle, and find the maximum sum of the weights of the sides that belong to that negative cycle. If such i, j does not exist, output "NA".

Constraints

The input satisfies the following conditions.

* 2 ≤ V ≤ 100000
* 1 ≤ E ≤ 500000
* -100 ≤ w <0
* 0 ≤ ci ≤ 100 (0 ≤ i ≤ E-1)
* 0 ≤ si, ti ≤ V-1 (0 ≤ i ≤ E-1)
* The same si and ti pair never appears while typing
* si and ti are different

Input


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


The number of vertices V, the number of edges E, and the weight w of the edge to be added are given in the first line, separated by blanks.

The information of the directed edge is given as si ti ci in the following E line. (0 ≤ i ≤ E-1)

This means that there is a directed edge of the weight ci from si to ti.

Output

Output the maximum value of the sum of the weights of the sides belonging to the negative cycle, which can be created by adding the directed side of the weight w, to one line. If a negative cycle cannot be created no matter where you add an edge, output "NA".

Examples

Input

3 2 -3
0 1 1
0 2 5


Output

-2


Input

3 2 -1
0 1 1
0 2 5


Output

NA


Input

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


Output

-1


Input

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


Output

-12

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T>ostream&operator<<(ostream &o,const vector<T>&t){o<<'[';FOR(i,t){if(i!=t.begin())o<<',';o<<*i;}return o<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)output(a[i],i!=n-1?',':10);}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

vector<int> tsort(const Graph &g) {
  int n = g.size();
  vector<int> num(n);
  REP(i, n) FOR(e, g[i]) num[e->dst]++;
  queue<int> Q;
  REP(i, n) if (num[i] == 0) Q.push(i);
  vector<int> res;
  while(!Q.empty()) {
    int v = Q.front(); Q.pop();
    res.push_back(v);
    FOR(e, g[v]) {
      if (num[e->dst]) {
        num[e->dst]--;
        if (num[e->dst] == 0) Q.push(e->dst);
      }
    }
  }
  REP(i, n) if (num[i]) return vector<int>();
  return res;
}
int dp[100000][101];
int main() {
  int n,m,w;
  while(input(n,m,w)) {
    Graph g(n);
    REP(i,m) {
      int s,t,c;
      input(s,t,c);
      g[s].push_back(Edge(s,t,c));
    }
    vector<int> order = tsort(g);
    memset(dp,0,sizeof(dp));
    // REP(i,n) dp[i][0] = 1;
    REP(i,n) {
      int id = order[i];
//      cout << id << endl;
      FOR(it, g[id]) {
        REP(j,101) {
          if (j+it->weight > 100) break;
          dp[it->dst][j+it->weight] |= dp[it->src][j];
          if (j == 0)
            dp[it->dst][j+it->weight] |= 1;
        }
      }
    }
    int ans = -INF;
    REP(i,n) {
      REP(j,101) {
        if (dp[i][j] && j+w<0) {
          chmax(ans, j+w);
        }
      }
    }
    if (ans == -INF) cout << "NA" << endl;
    else cout << ans << endl;
  }
}