//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define int ll
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;

    vector<pii> v[100001];
    ll ar[100001];
    int visited[100001];
    int isreach[100001];

        ll p;
    int n;

    vector<int> v3[100001];

    void dfs(int i)
    {
        visited[i]=1;
        isreach[i]=1;
        for(int j=0;j<v3[i].size();++j)
            if(visited[v3[i][j]]==0)
                dfs(v3[i][j]);
    }


    // a structure to represent a weighted edge in graph 
struct Edge { 
    int src, dest, weight; 
}; 
  
// a structure to represent a connected, directed and 
// weighted graph 
struct Graph { 
    // V-> Number of vertices, E-> Number of edges 
    int V, E; 
  
    // graph is represented as an array of edges. 
    struct Edge* edge; 
}; 
  
// Creates a graph with V vertices and E edges 
struct Graph* createGraph(int V, int E) 
{ 
    struct Graph* graph = new Graph; 
    graph->V = V; 
    graph->E = E; 
    graph->edge = new Edge[graph->E]; 
    return graph; 
} 
  
// The main function that finds shortest distances 
// from src to all other vertices using Bellman- 
// Ford algorithm.  The function also detects 
// negative weight cycle 
bool isNegCycleBellmanFord(struct Graph* graph, 
                           int src) 
{ 
    int V = graph->V; 
    int E = graph->E; 
    int dist[V]; 
    
    // Step 1: Initialize distances from src 
    // to all other vertices as INFINITE 
    for (int i = 0; i < V; i++) 
        dist[i] = INT_MAX; 
    dist[src] = 0; 
  
    // Step 2: Relax all edges |V| - 1 times. 
    // A simple shortest path from src to any 
    // other vertex can have at-most |V| - 1 
    // edges 
    for (int i = 1; i <= V - 1; i++) { 
        for (int j = 0; j < E; j++) { 
            int u = graph->edge[j].src; 
            int v = graph->edge[j].dest; 
            int weight = graph->edge[j].weight; 
            // cout<<u<<" "<<v<<endl;
            // cout<<u<<" "<<dist[u]<<endl;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
            {
                dist[v] = dist[u] + weight;
                //cout<<v<<"...."<<dist[v]<<endl; 
            }
        } 
    } 
  
    // Step 3: check for negative-weight cycles. 
    // The above step guarantees shortest distances 
    // if graph doesn't contain negative weight cycle. 
    // If we get a shorter path, then there 
    // is a cycle. 
    for (int i = 0; i < E; i++) { 
        int u = graph->edge[i].src; 
        int v = graph->edge[i].dest; 
        int weight = graph->edge[i].weight; 
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
            return true; 
    } 
  
    return false; 
} 



    class comp
    {
    public:
        bool operator() (const pii& i,const pii& j)
        {
            return i.f<j.f;
        }
    };



    void func(int s)
    {
        priority_queue<pii,vector<pii>,comp> pq;
        pq.push({0,s});
        visited[s]=1;
        pii x;
        int i,j;
        while(!pq.empty())
        {
            x=pq.top();
            pq.pop();
            i=x.s;
            //cout<<i<<" "<<x.f<<endl;
            if(x.f<ar[i])
            {
                continue;
            }
            for(j=0;j<v[i].size();++j)
            {
                //cout<<i<<" "<<v[i][j].f<<" "<<isreach[v[i][j].f]<<" "<<ar[v[i][j].f]<<" "<<x.f<<" "<<v[i][j].s<<" "<<p<<endl;
                if(isreach[v[i][j].f]==0)
                    continue;
                if(x.f+v[i][j].s-p>ar[v[i][j].f])
                {
                    pq.push({x.f+v[i][j].s-p,v[i][j].f});
                    ar[v[i][j].f] = x.f+v[i][j].s-p;   
                }
            }
        }
    }

    class triple
    {
    public:
        int a,b,c;
    };

    vector<triple> v2;



    signed main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int m,i,j,a,b,c;
            cin>>n>>m>>p;
            for(i=1;i<=m;++i)
            {
                cin>>a>>b>>c;
                v3[b].pb(a);
                v2.pb({a,b,c});
                v[a].pb({b,c});
            }
            dfs(n);
            for(i=1;i<=n;++i)
                ar[i]=-1e18;
            int E=0;
            for(i=0;i<v2.size();++i)
            {
                if(isreach[v2[i].b]==1)
                    ++E;
            }
            struct Graph* graph = createGraph(n, E);
            j=0;
            for(i=0;i<v2.size();++i)
            {
                if(isreach[v2[i].b]==1)
                {
                    //cout<<v2[i].a-1<<" "<<v2[i].b-1<<" "<<p-v2[i].c<<" "<<n<<endl;
                    graph->edge[j].src=v2[i].a-1;
                    graph->edge[j].dest=v2[i].b-1;
                    graph->edge[j].weight=p-v2[i].c;
                    ++j;
                }
            }
            if(isNegCycleBellmanFord(graph,0))
            {
                cout<<-1<<endl;
                return 0;
            }
            func(1);
            //cout<<n<<" "<<ar[n]<<endl;
            cout<<max(ar[n],0ll)<<endl;
        }
        return 0;
    }


Measured memory_bytes: 7936