stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

 

typedef long long ll;

typedef pair<int, int> P;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

 

template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}

template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}



const int NM = 2*1e5;

vector<int> graph[NM]; 

vector<int> Count(NM);

int n, q; 

void dfs(int now, int pre) {

    for(auto to : graph[now]) {

        if(to == pre) continue;

        Count[to] += Count[now];

        dfs(to, now);

    }

}

int main(){

    cin >> n >> q;

    for(int i=0; i<n-1;i++) {

        int a, b; cin >> a >> b;

        a--; b--;

        graph[a].push_back(b);

        graph[b].push_back(a);

    }

    Count.resize(n);

    rep(i, q) {

        int p, x; cin>>p>> x;

        p--;

        Count[p] += x;

    }

    dfs(0, -1);

    rep(i, n) {

        cout << Count[i] << ' ';

    }

    cout << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.1243482514041945x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}

template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}



const int NM = 2*1e5+10;

int ans[NM];

vector<vector<int>> g(NM);



void dfs(int now, int prev){

    ans[now] += ans[prev];

    for(auto next : g[now]){

        if(next == prev) continue;

        dfs(next, now);

    }

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n, q; cin>>n>>q;

    for(int i=1; i<=n-1; i++){

        int a, b; cin>>a>>b;

        g[a].push_back(b);

        g[b].push_back(a);

    }

    for(int i=1; i<=q; i++){

        int p, x; cin >> p>>x;

        ans[p] += x;

    }

    dfs(1, 0);

    for(int i=1;i<=n;i++){

        cout << ans[i] <<" ";

    }

}
// Slower C++ solution:
#include<list>

#include<iostream>

using namespace std;

int main(){

  int i;

  int n;

  long long c;

  for(;;){

    cin>>n;

    if(n==0)

      break;

    list<int> t;

    c=0;

    for(i=0;i<n;i++){

      int tmp;

      cin>>tmp;

      t.push_back(tmp);

    }

    t.sort();

    list<int>::iterator it=t.begin();

    for(i=0;i<n-1;i++){

      c+=(*it)*(n-i-1);

      it++;

    }

    cout<<c<<endl;

  }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.064594840455344x):
#include<algorithm>

#include<cstdio>

using namespace std;

int main(){

  int i;

  int n;

  while(scanf("%d",&n),n){

    int a[10000];

    for(i=0;i<n;++i)

      scanf("%d",a+i);

    sort(a,a+n);

    long long sm=0;

    for(i=0;i<n-1;++i)

      sm+=a[i]*(n-i-1);

    printf("%lld\n",sm);

  }

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;

vector<int>G[maxn];

int in[maxn],out[maxn],tol;

int sz[maxn],S[maxn],is[maxn],son[maxn];

void get_cal(int v,int fa,int limit)

{

	son[v]=0;

	if(v>=limit)

		return;

	son[v]=1;

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		get_cal(u,v,limit);

		son[v]+=son[u];

	}

}

void get_order(int v,int fa,int mx)

{

	is[v]=mx;

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		if(is[v]>is[fa]||v>is[v])

			get_cal(u,v,is[v]);

		sz[u]=son[u];

	}

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		get_order(u,v,max(mx,v));

	}

}

void dfs(int v,int fa)

{

	S[v]++;

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		S[v]+=sz[u];

	}

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		S[u]=S[v]-sz[u];

		dfs(u,v);

	}

}

int main()

{

	int n;scanf("%d",&n);

	for(int i=1;i<n;i++)

	{

		int x,y;scanf("%d%d",&x,&y);

		G[x].push_back(y);

		G[y].push_back(x);

	}

	get_order(1,0,0);

	dfs(1,0);

	for(int i=2;i<=n;i++)

		printf("%d ",S[i]-1);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.932964241042455x):
#include<cstdio>

#include<queue>

using namespace std;

#define N 200050

int fa[N],sz[N],head[N],cnt,mx[N],f[N],ti=1,as[N],n,a,b,fr[N],vl[N];

struct edge{int t,next;}ed[N*2];

priority_queue<pair<int,int> > st;

int finds(int x){return fa[x]==x?x:fa[x]=finds(fa[x]);}

void adde(int f,int t){ed[++cnt]=(edge){t,head[f]};head[f]=cnt;ed[++cnt]=(edge){f,head[t]};head[t]=cnt;}

void dfs1(int u,int fa){f[u]=fa;mx[u]=mx[f[u]],fr[u]=fr[f[u]];if(mx[u]<fa)mx[u]=fa,fr[u]=u;for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs1(ed[i].t,u);}

int que(int x){if(x<ti)return sz[finds(x)]-1;int as=0;for(int i=head[x];i;i=ed[i].next)if(ed[i].t<ti)as+=sz[finds(ed[i].t)];return as;}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<n;i++)scanf("%d%d",&a,&b),adde(a,b);

	for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;

	dfs1(1,0);

	for(int i=head[1];i;i=ed[i].next)st.push(make_pair(-1,ed[i].t));

	while(!st.empty())

	{

		int las=ti;

		ti=-st.top().first;int s=st.top().second;st.pop();

		for(int i=las;i<ti;i++)

		for(int j=head[i];j;j=ed[j].next)if(ed[j].t<i){int a=finds(i),b=finds(ed[j].t);fa[a]=b,sz[b]+=sz[a];}

		as[s]+=as[mx[s]]+que(s)+1-vl[fr[s]];

		for(int i=head[s];i;i=ed[i].next)if(ed[i].t!=f[s])st.push(make_pair(-mx[ed[i].t],ed[i].t)),vl[ed[i].t]=ed[i].t<ti?sz[finds(ed[i].t)]:0;

	}

	for(int i=2;i<=n;i++)printf("%d ",as[i]);

}//
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;

vector<int>G[maxn];

int in[maxn],out[maxn],tol;

int sz[maxn],S[maxn],is[maxn],son[maxn];

void get_cal(int v,int fa,int limit)

{

	son[v]=0;

	if(v>=limit)

		return;

	son[v]=1;

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		get_cal(u,v,limit);

		son[v]+=son[u];

	}

}

void get_order(int v,int fa,int mx)

{

	is[v]=mx;

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		if(is[v]>is[fa]||v>is[v])

			get_cal(u,v,is[v]);

		sz[u]=son[u];

	}

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		get_order(u,v,max(mx,v));

	}

}

void dfs(int v,int fa)

{

	S[v]++;

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		S[v]+=sz[u];

	}

	for(int i=G[v].size()-1;i>=0;i--)

	{

		int u=G[v][i];

		if(u==fa)

			continue;

		S[u]=S[v]-sz[u];

		dfs(u,v);

	}

}

int main()

{

	int n;scanf("%d",&n);

	for(int i=1;i<n;i++)

	{

		int x,y;scanf("%d%d",&x,&y);

		G[x].push_back(y);

		G[y].push_back(x);

	}

	get_order(1,0,0);

	dfs(1,0);

	for(int i=2;i<=n;i++)

		printf("%d ",S[i]-1);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.548146669027683x):
#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

using namespace std;



#define RG register int

#define LL long long



template<typename elemType>

inline void Read(elemType &T){

    elemType X=0,w=0; char ch=0;

    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}

    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();

    T=(w?-X:X);

}



struct edge{int Next,to;};

edge G[400010];

int head[200010],Max[200010],H[200010],F[200010],g[200010],Ans[200010];

int N,cnt=2;



inline void Add_Edge(int u,int v){

    G[cnt].to=v;

    G[cnt].Next=head[u];

    head[u]=cnt++;

}



int DFSB(int u,int fa,int x){

    if(u>x) return 0;

    int Res=1;

    for(int i=head[u];i;i=G[i].Next){

        int v=G[i].to;

        if(v==fa) continue;

        Res+=DFSB(v,u,x);

    }

    return Res;

}



void DFSA(int u,int fa){

    for(int i=head[u];i;i=G[i].Next){

        int v=G[i].to;

        if(v==fa) continue;

        Max[v]=max(Max[u],v);

        DFSA(v,u);

    }

    if(u>Max[fa]){

        H[u]=1;

        for(int i=head[u];i;i=G[i].Next){

            int v=G[i].to;

            if(v==fa) continue;

            F[v]=DFSB(v,u,u);

            g[v]=DFSB(v,u,Max[fa]);

            H[u]+=g[v];

        }

    }

    return;

}



void DFSC(int u,int fa){

    for(int i=head[u];i;i=G[i].Next){

        int v=G[i].to;

        if(v==fa) continue;

        Ans[v]=Ans[u];

        if(u>Max[fa]) Ans[v]+=F[v]-g[v];

        if(Max[v]>Max[u]) Ans[v]+=H[v];

        DFSC(v,u);

    }

    return;

}



int main(){

    Read(N);

    for(RG i=1;i<=N-1;++i){

        int u,v;Read(u);Read(v);

        Add_Edge(u,v);

        Add_Edge(v,u);

    }

    Max[1]=1;F[1]=1;DFSA(1,0);

    DFSC(1,0);

    for(RG i=2;i<=N;++i)

        printf("%d ",Ans[i]);

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

int n,tot;

const int N=200010;

int head[N],to[N<<1],nt[N<<1],ans[N],mx[N],fa[N],son[N],sf[N],sub[N];

vector<int>v[N];

void add(int f,int t)

{

	to[++tot]=t;nt[tot]=head[f];head[f]=tot;

}

namespace DSU

{

	int fa[N],siz[N];

	void YYCH(){for(int i=1;i<=n;++i)fa[i]=i,siz[i]=1;}

	int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}

	void he(int x,int y)

	{	

		x=find(x);y=find(y);if(x==y)return;

		fa[x]=y;siz[y]+=siz[x];

	}

}

void dfs1(int x,int fa)

{

	::fa[x]=fa;mx[x]=max(mx[fa],fa);sf[x]=son[mx[x]];

	for(int i=head[x];i;i=nt[i])

		if(to[i]!=fa)son[x]=to[i],dfs1(to[i],x);

}

void dfs2(int x,int fa)

{

	if(fa)ans[x]+=ans[mx[x]]-sub[son[mx[x]]]+1;

	for(int i=head[x];i;i=nt[i])

		if(to[i]!=fa)son[x]=to[i],dfs2(to[i],x);

}

int main()

{

	cin>>n;DSU::YYCH();

	for(int i=1,x,y;i<n;++i)

		scanf("%d%d",&x,&y),add(x,y),add(y,x);

	dfs1(1,0);

	for(int i=2;i<=n;++i)v[mx[i]].push_back(i);

	

	for(int i=1;i<=n;++i)

	{

		for(int j=0,siz=v[i].size();j<siz;++j)

		{

			int x=v[i][j];

			if(x<i)ans[x]=DSU::siz[DSU::find(x)]-1;

			else

			{

				if(x!=sf[x])ans[x]+=DSU::siz[DSU::find(sf[x])];

				for(int k=head[x];k;k=nt[k])

					if(to[k]!=fa[x]&&to[k]<i)

					{

						sub[to[k]]=DSU::siz[DSU::find(to[k])];

						ans[x]+=sub[to[k]];

					}

			}

		}

		for(int j=head[i];j;j=nt[j])

			if(to[j]<i)DSU::he(i,to[j]);

	}

	dfs2(1,0);

	for(int i=2;i<=n;++i)printf("%d ",ans[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.533787474890235x):
#include<bits/stdc++.h>

using namespace std;

const int N=500005;

struct ab{int f,t;} t[N];

int h,hh[N],vv[N],ans[N];

void make(int x,int y)

{

	t[++h].f=hh[x];

	t[h].t=y;

	hh[x]=h;

}

int dfs1(int x,int y,int z)

{

	if(x>z) return 0;

	int now=1;

	for(int i=hh[x];i;i=t[i].f)

	{

		int j=t[i].t;

		if(j==y) continue;

		now+=dfs1(j,x,z);

	}

	return now;

}

int dfs2(int x,int y,int z)

{

	int now=1;

	for(int i=hh[x];i;i=t[i].f)

	{

		int j=t[i].t;

		if(j==y) continue;

		if(j<z) now+=dfs2(j,x,z);

	}

	return now;

}

void dfs(int x,int y,int z,int v)

{

	if(x>z) v+=dfs2(x,y,z);

	ans[x]=v;

	for(int i=hh[x];i;i=t[i].f)

	{

		int j=t[i].t;

		if(j==y) continue;

		if(x>z) dfs(j,x,x,v+dfs1(j,x,x)-dfs1(j,x,z));

		else dfs(j,x,z,v);

	}

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=1;i<n;i++)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		make(x,y),make(y,x);

	}

	dfs(1,0,0,0);

	for(int i=2;i<=n;i++) printf("%d ",ans[i]-1);printf("\n");

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define MAX_V 100000

#define INF 1<<29

using namespace std;

struct edge{int to,cap,rev;};

vector<edge>G[MAX_V];

int level[MAX_V];

int iter[MAX_V];

void add_edge(int from,int to,int cap){

  G[from].push_back((edge){to,cap,(int)G[to].size()});

  G[to].push_back((edge){from,0,(int)G[from].size()-1});

}

void bfs(int s){

  memset(level,-1,sizeof(level));

  queue<int>q;

  level[s]=0;

  q.push(s);

  while(!q.empty()){

    int v=q.front();q.pop();

    for(int i=0;i<(int)(G[v].size());i++){

      edge &e=G[v][i];

      if(e.cap>0&&level[e.to]<0){

        level[e.to]=level[v]+1;

        q.push(e.to);

      }

    }

  }

}

int dfs(int v,int t,int f){

  if(v==t)return f;

  for(int &i=iter[v];i<(int)(G[v].size());i++){

    edge &e=G[v][i];

    if(e.cap>0&&level[v]<level[e.to]){

      int d=dfs(e.to,t,min(f,e.cap));

      if(d>0){

        e.cap-=d;

        G[e.to][e.rev].cap+=d;

        return d;

      }

    }

  }

  return 0;

}

int max_flow(int s,int t){

  int flow=0;

  while(1){

    bfs(s);

    if(level[t]<0)return flow;

    memset(iter,0,sizeof(iter));

    int f;

    while((f=dfs(s,t,INF))>0){

      flow+=f;

    }

  }

}

int main(){

  int x,y,n,s,t;

  vector<pair<int,int>> A,B;

  cin>>n;

  x=n;

  y=n;

  for(int i=0;i<n;i++){

  	cin>>s>>t;

  	A.push_back({s,t});

  }

  for(int i=0;i<n;i++){

  	cin>>s>>t;

  	B.push_back({s,t});

  }

  for(int i=0;i<n;i++){

  	for(int j=0;j<n;j++){

  		if(A[i].first<B[j].first&&A[i].second<B[j].second){

  			add_edge(i+1,n+j+1,1);

  		}

  	}

  }

  for(int i=0;i<y;i++){

  	add_edge(x+i+1,x+y+1,1);

  }

  for(int i=0;i<x;i++){

  	add_edge(0,i+1,1);

  }

  cout<<max_flow(0,x+y+1)<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 4.334897551514048x):
#include<bits/stdc++.h>

using namespace std;

const int maxn = 115;

int a[maxn], b[maxn], a1[maxn], b1[maxn];

int  v[maxn], match[maxn];

int n;

vector < int > g[maxn];

bool dfs(int x)

{

	int y;

	for(int i = 0; i < g[x].size(); i++){

		y = g[x][i];

		if(!v[y]){

			v[y] = 1;

			if(!match[y] || dfs(match[y])){

				match[y] = x;

				return true;

			}

		}

	}

	return false;

}

int main()

{

	scanf("%d", &n);

	for(int i = 1; i <= n; i++){

		scanf("%d %d", a + i, b + i);

	}

	for(int i = 1; i <= n; i++){

		scanf("%d %d", a1 + i, b1 + i);

	}

	for(int i = 1; i <= n; i++){

		for(int j = 1; j <= n; j++){

			if(a[i] < a1[j] && b[i] < b1[j]){

				g[i].push_back(j);

			}

		}

	}

//	for(int i = 1; i <= n; i++){

//		for(int j = 1; j <= n; j++){

//			printf("%d ", g[i][j]);

//		}

//		printf("\n");

//	}

	int ans = 0;

	for(int i  = 1; i <= n; i++){

		memset(v, 0, sizeof(v));

		if(dfs(i))ans++;

	}

	printf("%d", ans);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



int n, m, p;

vector<tuple<int, int, int>> edges;

vector<int> graph[2500];

vector<int> reverse_graph[2500];



bool can_reach_rev[2500];

bool can_reach[2500];



int coins[2500];



void dfs(int u) {

  if (can_reach[u]) {

    return;

  }

  can_reach[u] = true;

  for (int v : graph[u]) {

    dfs(v);

  }

}



void reverse_dfs(int u) {

  if (can_reach_rev[u]) {

    return;

  }

  can_reach_rev[u] = true;

  for (int v : reverse_graph[u]) {

    reverse_dfs(v);

  }

}



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0);

  cin >> n >> m >> p;



  for (int i = 0; i < n; i++) {

    coins[i] = INT_MIN/2;

  }



  for (int i = 0; i < m; i++) {

    int a, b, c;

    cin >> a >> b >> c;

    c -= p;

    a -= 1;

    b -= 1;

    graph[a].emplace_back(b);

    reverse_graph[b].emplace_back(a);

    edges.emplace_back(a, b, c);

  }

  dfs(0);

  reverse_dfs(n - 1);



  coins[0] = 0;

  for (int i = 0; i < n; i++) {

    for (auto t : edges) {

      int u, v, c;

      tie(u, v, c) = t;

      if (can_reach[u] && can_reach_rev[v]) {

        if (coins[u] + c > coins[v]) {

          coins[v] = coins[u] + c;

        }

      }

    }

  }

  for (auto t : edges) {

    int u, v, c;

    tie(u, v, c) = t;

    if (can_reach[u] && can_reach_rev[v]) {

      if (coins[u] + c > coins[v]) {

        printf("-1\n");

        return 0;

      }

    }

  }

  printf("%d\n", max(coins[n - 1], 0));

}

// Faster C++ solution for the same problem (measured speedup: 1.1267703279506711x):
// problem: longest distance from 0 to V-1, checking for positive cycle only on this path

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1 << 30;



struct Tadj {

	int id, w;

};

vector<vector<Tadj>> adjList;

int V;



vector<ll> ld;



vector<bool> visited;

void dfs(int u) {

   if (visited[u]) return;

   visited[u] = 1;

   for (Tadj v : adjList[u])

      dfs(v.id);

}



/* O(V*E) - retorna true se há um ciclo positivo entre 0 e V-1 */

bool belmman_ford(int s) {

   ld.assign(V, -INF); ld[s] = 0;



   ll first0, first1;

   for (int i = 0; i < V; i++) {

      // para cada aresta u --v.w--> v.id

      for (int u = 0; u < V; u++)

         for (Tadj v : adjList[u]) {

            if (ld[u] + v.w > ld[v.id] && ld[u] > -INF) {

               ld[v.id] = ld[u] + v.w;



               // se ainda conseguiu relaxar depois das V-1 vezes anteriores

               if (i == V-1) {

                  visited.assign(V, 0);

                  dfs(v.id);

                  if (visited[0] || visited[V-1]) return true;

               }

            }

         }

   }



   return false;

}



int main() {

   int E, P; cin >> V >> E >> P;

   adjList.assign(V, vector<Tadj>());

   while (E--) {

      int u, v, w; cin >> u >> v >> w; u--; v--; w -= P;

      adjList[u].push_back({v, w});

   }



   cout << (belmman_ford(0)? -1 : max(ld[V-1], 0ll)) << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)

#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)

#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)

#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)



/*

*/



ll n,m,p,dp[2510],dp2[2510],t;

vector<ll> v[2510],c[2510];



void init(){

	cin>>n>>m>>p;

	rep(i,m){

		ll a,b,x;

		cin>>a>>b>>x;

		v[a].push_back(b);

		c[a].push_back(x-p);

	}

	reg(i,1,n){

		dp[i]=-1e18;

		dp2[i]=-1e18;

	}

	dp[1]=0;

}



int main(void){

	init();

	reg(cnt,1,2*n){

		reg(i,1,n){

			rep(j,v[i].size()){

				if(dp2[v[i][j]]<dp[i]+c[i][j]){

					dp2[v[i][j]]=dp[i]+c[i][j];

				}

			}

		}

		if(cnt==n-1)t=dp2[n];

		reg(i,1,n)dp[i]=dp2[i];

	}

	if(dp[n]>t){

		cout<<-1<<endl;

	}else{

		cout<<max(t,0LL)<<endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.116906263869222x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)

#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)

#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)

#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)





// from: https://atcoder.jp/contests/abc137/submissions/6831647

template<typename T>

struct BellmanFord{

	struct edge{

		int u,v;

		T w;

		edge(){}

		edge(int u,int v,T w):u(u),v(v),w(w){}

	};



	int n;

	vector< vector<int> > G,Ginv;

	vector<int> reach;

	BellmanFord(int n):n(n),G(n),Ginv(n),reach(n,0){}



	vector<edge> es;

	void add_edge(int u,int v,T c){

		es.emplace_back(u,v,c);

		G[u].emplace_back(v);

		Ginv[v].emplace_back(u);

	}



	void dfs(int v){

		if(reach[v]) return;

		reach[v]=1;

		for(int u:Ginv[v]) dfs(u);

	}



	T build(int from,int to,int &neg_loop){

		dfs(n-1);

		const T INF = numeric_limits<T>::max();

		vector<T> ds(n,INF);

		ds[from]=0;

		for(int j=0;j<n;j++){

			bool update=0;

			for(auto e:es){

				if(!reach[e.u]||!reach[e.v]||ds[e.u]==INF) continue;

				if(ds[e.v]>ds[e.u]+e.w){

					ds[e.v]=ds[e.u]+e.w;

					update=1;

				}

			}

			if(!update) break;

			if(j==n-1){

				neg_loop=1;

				return INF;

			}

		}

		neg_loop=0;

		return ds[to];

	}

};



ll n,m,p,ans;



int main(){

	cin>>n>>m>>p;

	BellmanFord<ll> f(n);

	rep(i,m){

		ll a,b,x;

		cin>>a>>b>>x;

		f.add_edge(a-1,b-1,p-x);

	}

	int neg_loop;

	ans = f.build(0,n-1,neg_loop);

	cout<<(neg_loop?-1:max(-ans,0LL))<<endl;

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define MAX 5050

#define INF (1LL<<60LL)

typedef pair<int,int> P;

int V;

struct edge2{

  int from,to,cost;

  edge2(){}

  edge2(int from,int to,int cost):from(from),to(to),cost(cost){}

};

edge2 es[MAX];

int d[MAX];

int ok[MAX];

int used[MAX];

int shortest_path(int s,int e){

  for(int i=0;i<V;i++) d[i]=INF;

  d[s]=0;

  for(int j=0;j<V;j++){

    bool update=0;

    for(int i=0;i<e;i++){

      edge2 e=es[i];

      if(!ok[e.from]||!ok[e.to]) continue;

      if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){

        d[e.to]=d[e.from]+e.cost;

        update=1;

      }

    }

    if(!update) break;

    if(j==V-1){

      cout<<-1<<endl;

      exit(0);

    }

  }

  return d[V-1];

}



vector<int> G[MAX];

void dfs2(int v){

  if(used[v]) return;

  used[v]=1;

  for(int u:G[v]){

    dfs2(u);

  }

}



signed main(){

  int v,e,p;

  cin>>v>>e>>p;

  for(int i=0;i<e;i++){

    int u,v,d;

    cin>>u>>v>>d;u--;v--;

    G[u].push_back(v);

    es[i]=edge2(u,v,p-d);

  }

  for(int i=0;i<v;i++){

    memset(used,0,sizeof(used));

    dfs2(i);

    ok[i]=used[v-1];

  }

  V=v;

  cout<<max<int>(-shortest_path(0,e),0)<<endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1762134285190726x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}



//INSERT ABOVE HERE

template<typename T>

struct BellmanFord{

  struct edge{

    int u,v;

    T w;

    edge(){}

    edge(int u,int v,T w):u(u),v(v),w(w){}

  };



  int n;

  vector< vector<int> > G;

  vector<int> used,reach;

  BellmanFord(int n):n(n),G(n),used(n,0),reach(n,0){}



  vector<edge> es;

  void add_edge(int u,int v,T c){

    es.emplace_back(u,v,c);

    G[u].emplace_back(v);

  }



  void dfs(int v){

    if(used[v]) return;

    used[v]=1;

    for(int u:G[v]) dfs(u);

  }



  T build(int from,int to,int &neg_loop){

    for(int i=0;i<n;i++){

      fill(used.begin(),used.end(),0);

      dfs(i);

      reach[i]=used[to];

    }

    const T INF = numeric_limits<T>::max();

    vector<T> ds(n,INF);

    ds[from]=0;

    for(int j=0;j<n;j++){

      bool update=0;

      for(auto e:es){

        if(!reach[e.u]||!reach[e.v]||ds[e.u]==INF) continue;

        if(ds[e.v]>ds[e.u]+e.w){

          ds[e.v]=ds[e.u]+e.w;

          update=1;

        }

      }

      if(!update) break;

      if(j==n-1){

        neg_loop=1;

        return INF;

      }

    }

    neg_loop=0;

    return ds[to];

  }



};

signed main(){

  int n,m,p;

  cin>>n>>m>>p;

  BellmanFord<int> G(n);

  for(int i=0;i<m;i++){

    int a,b,c;

    cin>>a>>b>>c;

    a--;b--;

    G.add_edge(a,b,p-c);

  }

  int neg_loop;

  int res=G.build(0,n-1,neg_loop);

  if(neg_loop){

    cout<<-1<<endl;

    return 0;

  }

  cout<<max(-res,0)<<endl;

  return 0;

}