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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>

using namespace std;

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
template <typename T> void print_container(ostream& os, const T& c) { const char* _s = " "; if (!c.empty()) { __typeof__(c.begin()) last = --c.end(); foreach (it, c) { os << *it; if (it != last) os << _s; } } }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template <typename T> void print(T a, int n, const string& split = " ") { for (int i = 0; i < n; i++) { cout << a[i]; if (i + 1 != n) cout << split; } cout << endl; }
template <typename T> void print2d(T a, int w, int h, int width = -1, int br = 0) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
template <typename T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
#define dump(v) (cerr << #v << ": " << v << endl)

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define mp(a, b) make_pair(a, b)
#define ten(n) ((long long)(1e##n))

template <typename T, typename U> void upmin(T& a, const U& b) { a = min<T>(a, b); }
template <typename T, typename U> void upmax(T& a, const U& b) { a = max<T>(a, b); }
template <typename T> void uniq(T& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

typedef long long ll;
typedef pair<int, int> pint;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


int main()
{
    int n, m, w;
    scanf("%d%d%d", &n, &m, &w);
    const int max_x = -w - 1;

    static vector<pint> g[ten(5) + 1919];
    rep(i, m)
    {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        g[u].push_back(pint(v, c));
    }

    static bitset<128> dp[ten(5) + 1919];
    queue<pint> q;
    rep(i, n)
        q.push(pint(i, 0));
    while (!q.empty())
    {
        int pos = q.front().first;
        int cost = q.front().second;
        q.pop();
//         printf("%d %d\n", pos, cost);

        for (auto& e : g[pos])
        {
            int to = e.first;
            int ncost = cost + e.second;
            if (ncost <= max_x && !dp[to][ncost])
            {
                q.push(pint(to, ncost));
                dp[to][ncost] = true;
            }
        }
    }

    int mx = -1;
    rep(i, n) erep(j, max_x)
        if (dp[i][j])
            upmax(mx, j);
    if (mx == -1)
        puts("NA");
    else
        printf("%d\n", mx + w);
}