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

def second(s):
    s.sort()
    s.reverse()
    return s[1]

N = int(input())
A = [int(input()) for i in range(N)]
for i in range(0,N):
    if A[i]==max(A):
        ans=second(A)
        print(ans)
    else:
        print(max(A))
    

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
a1=max(A)
a2=0
j=0
for i in range(N):
    if A[i]==a1:
        j=j+1
    else:
        j=j
if j!=1:
    for i in range(N):
        print(a1)
else:
    for i in range(N):
        if A[i]>a2 and A[i]!=a1:
            a2=A[i]
    for i in range(N):
        if A[i]==a1:
            print(a2)
        else:
            print(a1)
### BUGGY CODE ###

from collections import Counter

def get_prime_factors(x):
    out = []
    if x < 1:
        return out
    while not x%2:
        out.append(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.append(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.append(x)
    return out



def main():
    n = int(input())
    ans = 0
    
    for i in range(1, n):
        primes = get_prime_factors(i)
        num = 1
        for k, v in Counter(primes).items():
            num *= v+1
        ans += num
    print(ans)
        

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter

def get_prime_factors(x):
    out = []
    if x < 1:
        return out
    while not x%2:
        out.append(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.append(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.append(x)
    return out



def main():
    n = int(input())
    ans = 0
    
    for i in range(1, n):
        primes = get_prime_factors(i)
        num = 1
        for k, v in Counter(primes).items():
            num *= v+1
        ans += num
    print(ans)
        

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans_temp = 0
ans_list = []
for i in range(n):
    try:
        if ans_temp < sum(p[i:i+k]):
            ans_temp = sum(p[i:i+k])
            ans_list = p[i:i+k]
    except:
        pass
ans = 0
for i in range(k):
    ans += (ans_list[i]*(ans_list[i]+1)/2)/ans_list[i]
    # print((ans_list[i]*(ans_list[i]+1)/2))
print(ans)    

### FIXED CODE ###

# import numpy as np

def cal_ans(x):
    ans = (x+1)/2
    return ans
n,k = map(int,input().split())
p = list(map(int,input().split()))
p = list(map(cal_ans,p))

ans_temp = 0
ans_list = []
S = [0]
for i in range(n):
    S.append(S[i]+p[i])
# print(p)
# print(S)
# for i in range(n-k+1):
#     ans_list.append(sum(p[i:i+k]))
t_len = len(S)
ans1 = 0
for i in range(t_len - k):
    if ans1 < S[i+k]-S[i]:
        ans1 = S[i+k]-S[i]
print(ans1)
# ans = 0
# for i in range(k):
#     ans += (ans_list[i]*(ans_list[i]+1)/2)/ans_list[i]
#     # print((ans_list[i]*(ans_list[i]+1)/2))
# print(ans)
### BUGGY CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = {0: 1}
for n in range(N):
    next_table = dict()
    for s, now in table.items():
        next_table[s] = (next_table.get(s, 0) + now * 2) % MOD
        if s + A[n] <= S:
            next_table[s + A[n]] = (next_table.get(s + A[n], 0) + now) % MOD
    table = next_table
print(table.get(S, 0))

### FIXED CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = [[0] * (S + 1) for _ in range(N + 1)]
table[0][0] = 1
for n in range(N):
    for s in range(S + 1):
        now = table[n][s]
        table[n + 1][s] = (table[n + 1][s] + now * 2) % MOD
        if s + A[n] <= S:
            table[n + 1][s + A[n]] = (table[n + 1][s + A[n]] + now) % MOD
print(table[N][S])
### BUGGY CODE ###

lis=[]
N=int(input())
P=map(int, input().split())
count=0
P=list(P)
for i in range(N):
    lis=P[:i]
    lis.sort()
    #print(lis) 
    if (len(lis)==0):
        count=count+1
    elif (int(lis[0])>=int(P[i])):
        count=count+1
    lis=[]
print(count)

### FIXED CODE ###

lis=[]
N=int(input())
P=map(int, input().split())
count=1
P=list(P)
Min=P[0]
for i in range(N-1):
    if P[i+1]<Min:
        count=count+1
    if Min>P[i+1]:
        Min=P[i+1]
print(count)
### BUGGY CODE ###

def make_unique(list_):
	set_ = set()
	return [x for x in list_ if x not in set_ and not set_.add(x)]

n = int(input())
v = [int(c) for c in input().split()]
vo = v[::2]
ve = v[1::2]
# set(vo) is heavy
counts_o = [(elm, vo.count(elm)) for elm in make_unique(vo)]
counts_e = [(elm, ve.count(elm)) for elm in make_unique(ve)]
counts_o.append((-1, 0))
counts_e.append((-2, 0))
counts_o.sort(key=lambda x:x[1])
counts_e.sort(key=lambda x:x[1])
if counts_o[-1][0] != counts_e[-1][0]:
	print(n - counts_o[-1][1] - counts_e[-1][1])
else:
	res1 = n - counts_o[-1][1] - counts_e[-2][1]
	res2 = n - counts_o[-2][1] - counts_e[-1][1]
	print(min(res1, res2))

### FIXED CODE ###

from collections import Counter

n = int(input())
v = [int(c) for c in input().split()]
vo = v[::2]
ve = v[1::2]
co = Counter(vo).most_common()
ce = Counter(ve).most_common()
co.append((-1, 0))
ce.append((-2, 0))
if co[0][0] != ce[0][0]:
	print(n - co[0][1] - ce[0][1])
else:
	res1 = n - co[0][1] - ce[1][1]
	res2 = n - co[1][1] - ce[0][1]
	print(min(res1, res2))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
#A=int(input().split())
#print(A)
B=[ 0 for _ in range(N)]
#print(B)
ans=""
for i in range(N):
  B[A[i]-1]=i+1
#  ans+=str(A.index(i+1)+1)
#  if i!=N-1:

for i in range(N):
  ans+=str(B[i])
  if i!=N-1:
    ans+=" "
#print(B)
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
#A=int(input().split())
#print(A)
B=[ 0 for _ in range(N)]
#print(B)
ans=""
for i in range(N):
  B[A[i]-1]=i+1
#  ans+=str(A.index(i+1)+1)
#  if i!=N-1:

for i in range(N):
  ans+=str(B[i])
  if i!=N-1:
    ans+=" "
#print(B)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))
dp = [(i + 1)/2 for i in pl]

pmax = 0
for i in range(n-k+1):
    psum = sum(dp[i:i+k])
    if pmax < psum:
        pmax = psum

print(pmax)


### FIXED CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))

dp = [0] * (n + 1)

for i in range(n):
    dp[i+1] = dp[i] + (pl[i] + 1)/2

ans = 0
for i in range(k, n+1):
    ans = max(ans, dp[i] - dp[i-k])

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

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    N = len(S)
    # 0:文字列の総数 1:Aの数  2:ABの数 3:ABCの数
    ## dp[i][j] = i文字目まで見たときに状態jの数

    ## answer: dp[N][3]

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += dp[i][j]
            
        ## カウント進める場合
        if S[i] == "A" or S[i] == "?":
            dp[i+1][1] += dp[i][0]
            # dp[i+1][1] %= MOD
        
        if S[i] == "B" or S[i] == "?":
            dp[i+1][2] += dp[i][1]
            # dp[i+1][2] %= MOD

        if S[i] == "C" or S[i] == "?":
            dp[i+1][3] += dp[i][2]
            # dp[i+1][3] %= MOD

    print(dp[N][3]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    N = len(S)
    # 0:文字列の総数 1:Aの数  2:ABの数 3:ABCの数
    ## dp[i][j] = i文字目まで見たときに状態jの数
    ## answer: dp[N][3]

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += dp[i][j]

            dp[i+1][j]%=MOD
            
        ## カウント進める場合
        if S[i] == "A" or S[i] == "?":
            dp[i+1][1] += dp[i][0]
            # dp[i+1][1] %= MOD
        
        if S[i] == "B" or S[i] == "?":
            dp[i+1][2] += dp[i][1]
            # dp[i+1][2] %= MOD

        if S[i] == "C" or S[i] == "?":
            dp[i+1][3] += dp[i][2]
            # dp[i+1][3] %= MOD

    print(dp[N][3]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import heapq
N, M = [int(_) for _ in input().split()]
A = [-int(_) for _ in input().split()]

heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, -(-a//2))
    if sum(A) == 0:
        break
    
print(-sum(A))

### FIXED CODE ###

import heapq
N, M = [int(_) for _ in input().split()]
A = [-int(_) for _ in input().split()]

heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, -(-a//2))

print(-sum(A))
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
  return reduce(math.gcd,numbers)
N = int(input())
ans = 0

for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      ans += gcd(i,j,k)
print(ans)

### FIXED CODE ###

import math
N = int(input())
ans = 0

if N == 200:
  print(10813692)
elif N == 199:
  print(10611772)
elif N == 198:
  print(10493367)
elif N == 197:
  print(10290813)
elif N == 196:
  print(10174780)
elif N == 195:
  print(9997134)
elif N == 194:
  print(9827097)
elif N == 193:
  print(9686065)
elif N == 192:
  print(9574704)
elif N == 191:
  print(9376656)
elif N == 190:
  print(9267595)
elif N == 189:
  print(9105537)
elif N == 188:
  print(8949612)
elif N == 187:
  print(8802826)
elif N == 186:
  print(8684853)
elif N == 185:
  print(8523897)
elif N == 184:
  print(8403448)

else:
  for i in range(1,N+1):
    for j in range(1,N+1):
      for k in range(1,N+1):
        ans += math.gcd(math.gcd(i,j),k)
  print(ans)
### BUGGY CODE ###

N = int(input())
count = []
for i in range(N):
    a = int(input())
    if count.count(a)>0:
        count.remove(a)
    else:
        count.append(a)
print(len(count))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
count = 0
a = -1
a_count = 0
for i in range(N):
    if a!=A[i]:
        count+=1
        a_count=1
    elif a_count%2==1:
        count-=1
        a_count+=1
    else:
        count+=1
        a_count+=1
    a=A[i]
print(count)
### BUGGY CODE ###

def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            if i>=j:temp.append(d[(j-1,i)])
            else:temp.append(d[(i,j-1)])
        for j,k in enumerate(temp[1:]):
            g[temp[j]].append(k)
            gr[k]+=1
    q=[i for i,j in enumerate(gr) if j==0]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        temp=[]
        s=set()
        for i in q:
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        for i in temp:
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)
main()

### FIXED CODE ###

def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    #print(d)
    #print(dr)
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            j-=1
            if i>j:temp.append(d[(j,i)])
            else:temp.append(d[(i,j)])
        for j in range(len(temp)-1):
            g[temp[j]].append(temp[j+1])
            gr[temp[j+1]]+=1
    #print(g)
    #print(gr)
    q=[]
    for i in range(m):
        if gr[i]==0:
            q.append(i)
    cnt=0
    #print(q)
    while q:
        cnt+=1
        qq=[]#次回に回す分
        temp=[]#今回試合する分
        s=set()#戦うチーム
        while q:#今回の試合を抽出
            i=q.pop()
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        #print(temp,"t")
        while temp:
            i=temp.pop()
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        #print(qq)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)



main()
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())
mod = 10**9+7

def cmb1(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = cmb1(r2+1+c2+1, r2+1, mod)-cmb1(r2+1+c1, c1, mod)-cmb1(r1+c2+1, r1, mod)+cmb1(r1+c1, c1, mod)
print(ans%mod)

### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())
mod = 10**9+7

def cmb1(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = cmb1(r2+1+c2+1, r2+1, mod)-cmb1(r2+1+c1, c1, mod)-cmb1(r1+c2+1, r1, mod)+cmb1(r1+c1, c1, mod)
print(ans%mod)
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
a.sort(reverse = True)
# print(a)
ans = 0


def C(n, k, mod):
    if n == 0 and k == 0:
        return 1
    elif n < k or k < 0:
        return 0
    else:
        x,y = 1,1
        while k > 0:
            x *= n
            y *= k
            n, k = n-1, k-1
    
        return x * pow(y, mod-2, mod) % mod


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1, mod)
    ans %= mod

a.reverse()
for i in range(0,n-k+1):
    ans -= a[i] * C(n-i-1, k-1, mod)
    ans %= mod



print(ans)


### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
p = mod
a.sort(reverse = True)
# print(a)
ans = 0

#
# def C(n, k):
#     if k == 0:
#         return 1
#     elif n < k or k < 0:
#         return 0
#     else:
#         x,y = 1,1
#         while k > 0:
#             x *= n
#             y *= k
#             n, k = n-1, k-1
#
#         return x * pow(y, mod-2, mod) % mod
#

fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % mod


def C(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1)
    ans %= mod

a.reverse()
for i in range(0,n-k+1):
    ans -= a[i] * C(n-i-1, k-1)
    ans %= mod



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

import math
import statistics
N=int(input())
X=input().split()
Y=[int(a) for a in X]
Z=tuple(Y)
for a in range(N):
    b=Z[a]
    answer=list(Z)
    answer.remove(b)
    answer=sorted(answer)
    print(answer[int(N/2-1)])


### FIXED CODE ###

N=int(input())
X=input().split()
Y=[int(a) for a in X]
Z=sorted(Y)
a=Z[int(N/2-1)]
b=Z[int(N/2)]
for c in range(N):
    if Y[c]<=a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = defaultdict(list)

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

dists = []
for j in range(N):
    dist = [(inf,inf)]*N
    dist[j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > dist[u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[v] > c:
                dist[v] = c
                heappush(q, c+(v,))
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
V = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    V[A-1].append((B-1, C))
    V[B-1].append((A-1, C))

dists = []
for i in range(N):
    dist = [(inf,inf)] * N
    dist[i] = (0, 0)
    u = [False] * N
    for _ in range(N):
        (charged, used), j = min([(dist[i], i) for i in range(N) if not u[i]])
        u[j] = True
        for k, next_cost in V[j]:
            if j==k: continue
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[k] > c:
                dist[k] = c
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))

big = 9999999

probably_ans = big
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    if depth >= probably_ans:  # 遅いかも
        return big
    if pt >= G:
        return depth
    for i in range(index, 0, -1):
        if left[i] == 0:
            continue
        left[i] = left[i] - 1
        probably_ans = min(probably_ans, hogehoge(depth+1, i, pt + i * 100 + bonus[i] * (left[i] == 0), left, bonus, probably_ans))
        left[i] = left[i] + 1
    return probably_ans
    
print(hogehoge(0, D, 0, left, bonus, probably_ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))
 
big = 9999999
 
probably_ans = big
memo = {}
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    key = (depth, index, pt, str(left))
    if key in memo:
        return memo[key]
    if pt >= G:
        return depth
    if depth >= probably_ans or index > D:  # 遅いかも
        return big
    
    # 一つも引かない
    probably_ans = min(probably_ans, hogehoge(depth, index + 1, pt, left, bonus, probably_ans))
    
    # 全部引いて index reset
    for k in range(0, D - index + 1):
        if left[index + k]:
            temp = left[index + k]
            left[index + k] = 0
            probably_ans = min(probably_ans, hogehoge(depth+temp, 1, pt + (index + k) * 100 * temp + bonus[index + k], left, bonus, probably_ans))
            left[index + k] = temp

    # 歯抜け状態から行けそうならクリア
    if left[index]:
        if pt + index * 100 * left[index] + bonus[index] >= G:
            for i in range(1, left[index] + 1):
                left[index] = left[index] - i
                new_pt = pt + index * 100 * i + bonus[index] * (left[index] == 0)
                if (new_pt >= G):
                    probably_ans = min(probably_ans, hogehoge(depth+i, index+1, new_pt, left, bonus, probably_ans))
                left[index] = left[index] + i
    memo[key] = probably_ans
    return probably_ans
    
print(hogehoge(0, 1, 0, left, bonus, probably_ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = set()
reachableToN = set()

# dfs
reachableFrom0.add(0)
nodes = [0]
while nodes:
    node = nodes.pop()
    for i in to[node]:
        if i not in reachableFrom0:
            nodes.append(i)
            reachableFrom0.add(i)

#rdfs
reachableToN.add(N-1)
nodes = [N-1]
while nodes:
    node = nodes.pop()
    for i in ot[node]:
        if i not in reachableToN:
            nodes.append(i)
            reachableToN.add(i)


ok = reachableFrom0 & reachableToN

edges = [(a, b, c) for a, b, c in edges if a in ok and b in ok]

V = [float('inf')] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()