/*Replace each edge with weight c with an edge of weight −c+p. Now the problem becomes to find the
minimum weight path from 1 to n. This can easily be done by Bellman-Ford. The answer would be the
maximum of 0 and the negative distance from 1 to n in the new graph.

One thing to note however is that it is not sufficient to check if a negative weight
cycle exists but to find a negative weight cycle on the path from 1 to n. However,
a slight modification in the negative weight cycle detection algorithm allows it. Here's the code.

Edit: As AlwaysMerlin pointed out there's indeed a problem with my submission. The main idea is 
correct, it is the handling of negative weight cycles that cause a problem. The code above tries to 

check if there exists a negative weight cycle from 1 to n by checking if the distance of vertex n ever
changes after n−1 rounds, if so there exists a negative weight cycle on the path from 1 to n. While 
this indeed is a necessary, this is not sufficient. Since the number of rounds required to reduce the
distance from 1 to n maybe on the order of the weight of the edges.

The way to fix it is to assign −∞ distance to any node whose distance decreases after the first n−1 
rounds and run the algorithm for n−1 more rounds. This way, if the distance of a node reduces,
the distance of all its neighbours is guaranteed to reduce in the next turn, unlike with our
previous algorithm. Eventually, all the nodes whose distance can be reduced will become −∞ by 
the end of it and we simply need to check if the distance of n is −∞.

*/


















#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
# define  pii pair<ll,ll> 
# define pb push_back
# define f first 
# define s second 



class Edge
{
    public:
    ll src;
    ll des;
    ll cost;
};

ll dist[100001];

const ll inf=1e18;


int main()
{
    ll n,m,p;
    cin>>n>>m>>p;
    
    vector<Edge> E;
   
    for(ll i=0;i<m;i++)
    {
       
        ll x,y,c;
        cin>>x>>y>>c;
        
        Edge node;
        
        node.src=x;
        node.des=y;
        node.cost=-c+p;
        
        E.pb(node);
    }
    
    fill(dist,dist+n+1,inf);
    
   
    
    dist[1]=0;
    
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<E.size();j++)
        {
            ll sr=E[j].src;
            ll de=E[j].des;
            ll co=E[j].cost;
            
            if(dist[sr]!=inf && dist[de]>dist[sr]+co)
                {
                    dist[de]=dist[sr]+co;
                }
        }
    }
    
    
     for(int j=0;j<E.size();j++)
        {
            ll sr=E[j].src;
            ll de=E[j].des;
            ll co=E[j].cost;
            
            if(dist[sr]!=inf && dist[de]>dist[sr]+co)
                {
                    dist[de]=-inf;
                }
        }
        
        
       for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<E.size();j++)
        {
            ll sr=E[j].src;
            ll de=E[j].des;
            ll co=E[j].cost;
            
            if(dist[sr]!=inf && dist[de]>dist[sr]+co)
                {
                    dist[de]=-inf;
                }
        }
    } 
    
    
    if(dist[n]==-inf) cout<<"-1"<<endl;
    else
    {
        cout<<max(-dist[n],(ll)0)<<endl;
    }
        
        
  
    
    
    

	
	return 0;
}


Measured memory_bytes: 576