Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())

for n in range(1, N+1):
    s = n//5
    cnt = 0
    flag = 0
    for x in range(1, s+1):
        for y in range(1, s+1):
            for z in range(1, s+1):
                siki = x**2 + y**2 + z**2 + x*y + y*z + z*x

                if siki == n:
                    # print('ans = ', siki)
                    if (x==y)and(y==z):
                        cnt += 1
                    elif (x!=y)and(y!=z):
                        cnt += 6
                    else:
                        cnt += 3
                # elif siki > n:
                    flag = 1
                    break
                elif siki > n:
                    break
            if flag:
                break
        if flag:
            break
    print(cnt)

### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

x = int(input())
def bs(n):
    l = -1000
    r = n
    while r-l>=0:
        mid = (l+r)>>1
        tmp = pow(mid,5)
        if tmp==n:
            return True, mid
        elif tmp<n:
            #print(mid,tmp,n)
            l = mid+1
        else:
            r = mid
    if pow(l,5)==n:
        return True,l
    return False,0
for i in range(-1000,1000):
    key = pow(i,5)-x
    f,b = bs(key)
    if f:
        print(i,b)
        break


### FIXED CODE ###

from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------
x = int(input())
def power(x,y):
    res = 1
    #print(x,y)
    while y>0:
        if y%2:
            res*=x
        x*=x
        y//=2
        #print(x,y)
    return res
def bs(n):
    l = -250
    r = 250
    while r-l>=0:
        mid = (l+r)//2
        tmp = power(mid,5)
        if tmp==n:
            return True, mid
        elif tmp<n:
            #print(mid,tmp,n)
            l = mid+1
        else:
            r = mid-1
    if power(l,5)==n:
        return True,l
    elif power(r,5)==n:
        return True,r
    return False,0
for i in range(-250,250):
    key = power(i,5)-x
    f,b = bs(key)
    if f:
        print(i,b)
        break
### BUGGY CODE ###

N, K = map(int, input().split())
h_in = []
[h_in.append(int(input())) for i in range(N)]
import itertools

h = []
for l in itertools.combinations(h_in,K):
    h.append(max(l) - min(l))
print(min(h))

### FIXED CODE ###

N, K = map(int, input().split())
h = []
[h.append(int(input())) for i in range(N)]

h.sort()
l = []
for i in range(N-K+1):
    l.append(h[i+K-1] - h[i])
print(min(l))
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().strip().split()))
ans = 0
for i in range(N):
    for j in range(N):
        if i != j:
            if array[i] % array[j] == 0 or array[i] == array[j] :
                break
        if j == N-1:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ans = 0
a = [True] * (10**6 + 1)
i = 0
before = 0
for i in array:
    if a[i] == True:
        j = 2*i
        if i == before:
            a[i] = False
        while j <= array[N-1]:
            a[j] = False
            j += i
        before = i
for i in array:
    if a[i] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

def main():
    import sys
    n=int(sys.stdin.readline())
    m=(n-1)//2+2
    x=tuple(map(int,input().split()))
    x = (0,) + x + (0,)
    for i in range(n):
        print(sorted(x[:i+1]+x[i+2:])[m])
if __name__ == '__main__':
    main()

### FIXED CODE ###

# ABC094C - Many Medians (ARC095C)
def main():
    n = int(input())
    x = list(map(int, input().split()))
    # 偶数個の数から一つ数を取り除いたものの中央値はl,hのいずれか.
    l, h = sorted(x)[n // 2 - 1 : n // 2 + 1]
    ans = [h if e <= l else l for e in x] # l以下の値を取り除いたならば中央値はh
    print("\n".join(map(str, ans)))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    que = deque([])
    maze = [[f_inf] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "#":
                que.append([h, w])
                maze[h][w] = 0

    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            if maze[next_h][next_w] > maze[h][w] + 1:
                maze[next_h][next_w] = maze[h][w] + 1
                que.append([next_h, next_w])

    res = 0
    for h in range(H):
        for w in range(W):
            res = max(res, maze[h][w])
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

cnt = [[-1]*W for _ in range(H)]

que = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            que.append((h, w))
            cnt[h][w] = 0

ans = 0
while que:
    h, w = que.popleft()
    ans = cnt[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        next_h = h + dy
        next_w = w + dx
        if next_h < 0 or H <= next_h or next_w < 0 or W <= next_w:
            continue
        if cnt[next_h][next_w] == -1:
            cnt[next_h][next_w] = ans+1
            que.append((next_h, next_w))

print(int(ans))
### BUGGY CODE ###

s = input()
k = int(input())

sset = set()

for i in range(1, len(s)+1):
    sset |= set([s[j:j+i] for j in range(0, len(s))])

print(sorted(sset)[k-1])

### FIXED CODE ###

s = input()
k = int(input())

sset = set()

for i in range(1, 6):
    sset |= set([s[j:j+i] for j in range(0, len(s))])

print(sorted(sset)[k-1])
### BUGGY CODE ###

n = int(input())
strs = [sorted(str(input())) for _ in range(n)]

cnt = 0
for i in range(n):
  cnt += strs[i+1:].count(strs[i])
print(cnt)

### FIXED CODE ###

n = int(input())
strs = ["".join(sorted(str(input()))) for _ in range(n)]

cache = {}
cnt = 0
for s in strs:
  if s in cache.keys():
    cnt = cnt + cache[s]
    cache[s] = cache[s] + 1
  else:
    cache[s] = 1
print(cnt)
### BUGGY CODE ###

import numpy as np
from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    a = np.asarray(a)
    dp = np.zeros((N+1,S+1,3))
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0] ;dp[i+1][j][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(int(dp[N][S][2]))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [0]*(S+1)
    ans = 0
    for A in a:
        dp[0] += 1
        for i in reversed(range(A,S+1)):
            dp[i] += dp[i-A]    
            dp[i] %= mod
        ans += dp[S]
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
count = 0
List = list(map(int, input().split()))
for i in range(N):
  for j in range(N):
    for k in range(N):
      a = List[i]
      b = List[j]
      c = List[k]
      if i != j and i != k and k != j:
        if a+b>c and a+c>b and b+c>a:
          count += 1
print(int(count/6))

### FIXED CODE ###

import bisect
N = int(input())
count = 0
List = sorted(list(map(int, input().split())))
for i in range(N-2):
  for j in range(N-i-2):
    a = List[i]
    b = List[i+j+1]
    index = bisect.bisect_left(List, a+b)
    count += index-i-j-2
print(count)
### BUGGY CODE ###

def remaining(s1, s2):
    if not("R" in [s1, s2]):
        return "R"
    elif not("B" in [s1, s2]): 
        return "B"
    else:
        return "G"

N = int(input())
S = list(input())

num_R = [0 for _ in range(N)]
num_G = [0 for _ in range(N)]
num_B = [0 for _ in range(N)]
if S[-1] == "R":
    num_R[-1] = 1
elif S[-1] == "B":
    num_B[-1] = 1
else:
    num_G[-1] = 1

for i in range(N-2, -1, -1): 
    if S[i]=="R":
        num_R[i] = num_R[i+1]+1
        num_G[i] = num_G[i+1]
        num_B[i] = num_B[i+1]
    elif S[i]=="G":
        num_R[i] = num_R[i+1]
        num_G[i] = num_G[i+1]+1
        num_B[i] = num_B[i+1]
    else:
        num_R[i] = num_R[i+1]
        num_G[i] = num_G[i+1]
        num_B[i] = num_B[i+1]+1

if __name__ == "__main__":
    ans = 0
    for i in range(0, N-2):
        for j in range(i+1, N-1):
            if S[i] == S[j]:
                continue
            target = remaining(S[i], S[j])
            if target == 'R':
                num = num_R
            elif target == 'G':
                num = num_G
            else:
                num = num_B

            ans += num[j+1]
            if j+(j-i) < N:
                if S[j+(j-i)]==target:
                    ans -= 1
    print(ans)

### FIXED CODE ###

def remaining(s1, s2):
    if not("R" in [s1, s2]):
        return "R"
    elif not("B" in [s1, s2]): 
        return "B"
    else:
        return "G"

N = int(input())
S = list(input())

num_R = [0 for _ in range(N)]
num_G = [0 for _ in range(N)]
num_B = [0 for _ in range(N)]
if S[-1] == "R":
    num_R[-1] = 1
elif S[-1] == "B":
    num_B[-1] = 1
else:
    num_G[-1] = 1

for i in range(N-2, -1, -1): 
    if S[i]=="R":
        num_R[i] = num_R[i+1]+1
        num_G[i] = num_G[i+1]
        num_B[i] = num_B[i+1]
    elif S[i]=="G":
        num_R[i] = num_R[i+1]
        num_G[i] = num_G[i+1]+1
        num_B[i] = num_B[i+1]
    else:
        num_R[i] = num_R[i+1]
        num_G[i] = num_G[i+1]
        num_B[i] = num_B[i+1]+1

if __name__ == "__main__":
    ans = 0
    for i in range(0, N-2):
        for j in range(i+1, N-1):
            if S[i] == S[j]:
                continue
            target = remaining(S[i], S[j])
            if target == 'R':
                num = num_R
            elif target == 'G':
                num = num_G
            else:
                num = num_B

            ans += num[j+1]
            if j+(j-i) < N:
                if S[j+(j-i)]==target:
                    ans -= 1
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = input()
power = 1
for i in range(N):
    power = power*(i+1)

print(power%1000000007)

### FIXED CODE ###

# -*- coding: utf-8 -*-

import math

N = input()
power = 1
for i in range(N):
    power = math.fmod(power*(i+1),1000000007)

print(int(power))
### BUGGY CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))

if N >= M:
  print(0)
else:
  X.sort()
  D = []
  for i in range(len(X)-1):
    D.append(abs(X[i] - X[i+1]))
    D.sort()
  print(sum(D[0:M-N]))

### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
X = list(map(int, input().split()))

if N >= M:
  print(0)
else:
  X.sort()
  npX = np.array(X)
  D = npX[1:] - npX[:-1]
  D.sort()
  print(sum(D[0:M-N]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline


n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

for i in range(m):
    a, b, c = list(map(int, input().split()))
    adjmatrix[a-1][b-1] = c
    adjmatrix[b-1][a-1] = c

#print(abc)

#costmatrix = wf(adjmatrix)
for k in range(len(adjmatrix)):
    for i in range(len(adjmatrix)):
        for j in range(len(adjmatrix[i])):
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				

        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(route)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)
        
        

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

import math
from itertools import permutations

#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]				
	return glath

N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 
r=[int(x) for x in str(input()).split()]
graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c

#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


max_count=float("inf")
for i in permutations(r):
        cost=0
        for j in range(len(i)-1):                
                cost+= all_cost[i[j]-1][i[j+1]-1]       
        max_count=min(max_count,cost)

print(max_count)
### BUGGY CODE ###

N = int(input())
S = input()
sl = list(S)
min_turn = 300000
for i in range(N):
    if i == 0:
        turn = sl[1:].count('E')
    elif i == (N-1):
        turn = sl[0:i].count('W')
    else:
        turn = sl[0:i].count('W') + sl[i+1:].count('E')
    if min_turn > turn:
        min_turn = turn
print(min_turn)

### FIXED CODE ###

N = int(input())
S = input()
min_turn = 300000
wnum = 0
for i in range(N):
    if i == 0:
        enum = S[1:].count('E')
    if (1 <= i) and (S[i] == 'E'):
        enum -= 1
    if (1 <= i) and (S[i-1] == 'W'):
        wnum += 1
    turn = enum + wnum
    if min_turn > turn:
        min_turn = turn
print(min_turn)
### BUGGY CODE ###

N = int(input())
s = [input() for _ in range(N)]
os = [ "" for _ in range(N) ]

for i in range(N):
    os[i] = sorted(s[i])
#print(os)
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        #print(dicts[i], dicts[j])
        if os[i] == os[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
s = [input() for _ in range(N)]
dic = defaultdict(int)

for i in range(N):
    os = "".join(sorted(s[i]))
    dic[os] += 1
#print(os)
cnt = 0
for s, c in dic.items():
    #print(s, c)
    cnt += c * (c-1) // 2
    #print(c* (c - 1) // 2)
print(cnt)
### BUGGY CODE ###

K = int(input())
bc = []


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


fin = 0
for a in range(K):
    bc = []
    for b in range(K):
        for c in range(K):
            ans = gcd(b+1, c+1)
            bc.append(ans)
    fin += sum([gcd(a+1, i) for i in bc])

print(fin)


### FIXED CODE ###

K = int(input())


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


ans = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            ans += gcd(gcd(a+1, b+1), c+1)

print(ans)
### BUGGY CODE ###

from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    Q =     _in[1]   # type:str
    Q_arr = []
    for __in in _in[2:]:
        _ = __in.split(' ')
        if len(_) == 1:
            Q_arr.append([int(_[0])])
        else:
            Q_arr.append([int(_[0]),int(_[1]),_[2]])
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    for _Q in Q_arr:
        if _Q[0] == 1:
            S = S[::-1]
        elif _Q[1] == 1:
            S = _Q[2] + S
        else:
            S = S + _Q[2]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(S)


### FIXED CODE ###

from sys import stdin
from collections import deque

if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    Q =     _in[1]   # type:str
    Q_arr = []
    for __in in _in[2:]:
        _ = __in.split(' ')
        if len(_) == 1:
            Q_arr.append([int(_[0])])
        else:
            Q_arr.append([int(_[0]),int(_[1]),_[2]])
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    S_arr = deque([s for s in S])
    reverse = False
    for _Q in Q_arr:
        if _Q[0] == 1:
            reverse = not reverse
        elif (_Q[1] == 1 and (not reverse)) or (_Q[1] == 2 and reverse):
            S_arr.appendleft(_Q[2])
        else:
            S_arr.append(_Q[2])
    if reverse:
        S_arr.reverse()
    S_arr = list(S_arr)
    S = ''.join(S_arr)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(S)
### BUGGY CODE ###

N, M = map(int, input().split())

mod_num = 10 ** 9 + 7
a = [0] * M

for i in range(M):
    a[i] = int(input())

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if i in a:
        val[1] = 0

 
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

print(ans % (10**9 +7))
### BUGGY CODE ###

      
def binary_search(A,n):
    # sequence A, item n
    l = len(A)
    if l==0:
        return False
    elif A[l/2] > n:
        return binary_search(A[:l/2],n)
    elif A[l/2] == n:
        return True
    elif A[l/2]<n:
        return binary_search(A[(l/2)+1:],n)

n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())

C = 0
for k in T:
    if binary_search(S,k):
        C += 1
print C

### FIXED CODE ###

# coding: utf-8
# Here your code !
n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())
C = 0

def binary_search(A,n):
    """no recursion version"""
    l = len(A)
    left = l/2
    right = l-1
    while A[left] != n:
        if left == right and A[left] != n:
            #print left,right,"if"
            return False
        elif A[left] > n: # n????????????????????´???
            right = left
            left = left/2
            #print left,right,"elif1"
        elif A[left] < n: # n????????????????????´???
            right = right
            left = (left + right-1)/2 + 1
            #print left,right,"elif2"
    else:
        return True

for item in T:
    if binary_search(S,item):
        C += 1
print C
### BUGGY CODE ###

N = int(input())
S = list(input())
for i in range(N):
    turn_sum = len([S[q] for q in range(N) if (i < q and S[q] == "E") or (i > q and S[q] == "W")])
    if i == 0:
        min = turn_sum
    if min > turn_sum:
        min = turn_sum
print(min)

### FIXED CODE ###

N = int(input())
S = list(input())
w_count = 0
e_count = 0
count_sum = [0 for k in range(N)]
for i in range(1,N):
    if S[i - 1] == "W":
        w_count += 1
    count_sum[i] += w_count
for q in range(N-2,-1,-1):
    if S[q + 1] == "E":
        e_count += 1
    count_sum[q] += e_count
print(min(count_sum))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)


N,Q=map(int,input().split())

A=[[] for i in range(N)]
c=[0]*N

for i in range(N-1):
    a,b=map(int,input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)

for i in range(Q):
    p,x=map(int,input().split())
    c[p-1]+=x

def dfs(now,prev=-1):
    for next in A[now]:
        if next==prev:continue
        else:
            c[next]+=c[now]
            dfs(next,now)
dfs(0)
print(*c)


### FIXED CODE ###

import sys
input=sys.stdin.readline

sys.setrecursionlimit(10**6)


N,Q=map(int,input().split())

A=[[] for i in range(N)]
c=[0]*N

for i in range(N-1):
    a,b=map(int,input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)

for i in range(Q):
    p,x=map(int,input().split())
    c[p-1]+=x

def dfs(now,prev=-1):
    for next in A[now]:
        if next==prev:continue
        else:
            c[next]+=c[now]
            dfs(next,now)
dfs(0)
print(*c)
### BUGGY CODE ###

import sys


def solve(n, links, parents, costs):
    q = [n - 1]
    reachable = set()
    while q:
        v = q.pop()
        if v in reachable:
            continue
        reachable.add(v)
        q.extend(u for u in parents[v] if u not in reachable)

    for v in reachable:
        links[v] &= reachable

    INF = 10 ** 12
    dist = [INF] * n
    dist[0] = 0
    for _ in range(len(reachable)):
        updated = False
        for v in reachable:
            d = dist[v]
            if d == INF:
                continue
            cv = costs[v]
            for u in links[v]:
                if dist[u] > d + cv[u]:
                    dist[u] = d + cv[u]
                    updated = True
        if not updated:
            break
    else:
        return -1

    return max(0, -dist[n - 1])


n, m, p = list(map(int, input().split()))
INF = 10 ** 12
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
costs = [[INF] * n for _ in range(n)]
for line in sys.stdin:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    parents[b].add(a)
    costs[a][b] = min(costs[a][b], p - c)

print(solve(n, links, parents, costs))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 5)


def omit(n, links, parents):
    q = [0]
    visited_f = [False] * n
    while q:
        v = q.pop()
        if visited_f[v]:
            continue
        visited_f[v] = True
        q.extend(u for u in links[v] if not visited_f[u])

    q = [n - 1]
    visited_b = [False] * n
    while q:
        v = q.pop()
        if visited_b[v]:
            continue
        visited_b[v] = True
        q.extend(u for u in parents[v] if not visited_b[u])

    remains = [i for i, (f, b) in enumerate(zip(visited_f, visited_b)) if f and b]
    sr = set(remains)
    for v in remains:
        links[v] &= sr

    return remains


n, m, p = list(map(int, input().split()))
INF = 10 ** 12
costs = [[INF] * n for _ in range(n)]
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
for line in sys.stdin:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    parents[b].add(a)
    costs[a][b] = min(costs[a][b], p - c)
remains = omit(n, links, parents)

dist = [INF] * n
dist[0] = 0
for _ in range(n + 1):
    updated = False
    for v in remains:
        d = dist[v]
        if d == INF:
            continue
        cv = costs[v]
        for u in links[v]:
            if dist[u] > d + cv[u]:
                dist[u] = d + cv[u]
                updated = True
    # print(dist, updated)
    if not updated:
        break
else:
    print(-1)
    exit()

print(max(0, -dist[n - 1]))