Harryxun/stf_run huggingface dataset:
^CTraceback (most recent call last):
  File "testcon1.py", line 6, in <module>
    if x>=x2 and x<=y2:
N,K = map(int,input().split())
okashi=[0] * N
for i in range(K):
  x=input()
  y=input().split()
  for j in y:
    okashi[int(j)-1]=1
counter=0

for i in okashi:
  if i==0:
    counter=counter+1
print(counter)

### FIXED CODE ###

N,K = map(int,input().split())
okashi=[0] * N
for i in range(K):
  x=input()
  y=input().split()
  for j in y:
    okashi[int(j)-1]=1
counter=0

for i in okashi:
  if i==0:
    counter=counter+1
print(counter)
A, B, C, D, E, F = [int(_) for _ in input().split()]
if A==1:
  raise


def main(A, B, C, D, E, F):
    conc = -1
    ans = (1, 2)
    for na in range(F // (100 * A) + 1):
        for nb in range(F // (100 * B) + 1):
            if na == nb == 0:
                continue
            G = F - na * 100 * A - nb * 100 * B
            for nc in range(G // C + 1):
                for nd in range(G // D + 1):
                    W = na * 100 * A + nb * 100 * B + nc * C + nd * D
                    if 0 < W <= F and nc * C + nd * D <= E * (na * A + nb * B):
                        conc2 = 100 * (nc * C + nd * D) / W
                        if conc < conc2 <= 100 * E / (100 + E):
                            ans = (W, nc * C + nd * D)
                            conc = conc2
    return ans


print(*main(A, B, C, D, E, F))


### FIXED CODE ###

import itertools
A, B, C, D, E, F = [int(_) for _ in input().split()]
W = [0] * (F+1)
S = [0] * (F+1)
for a, b in itertools.product(range(F // (100*A) + 1), range(F//(100*B) + 1)):
    if 100*A*a+100*B*b <= F:
        W[100*A*a+100*B*b] = min(E*(A*a+B*b), F-100*A*a-100*B*b)

for c, d in itertools.product(range(F // C + 1), range(F // D + 1)):
    if C*c+D*d <= F:
        S[C*c+D*d] = C*c+D*d
for i in range(F):
    if S[i+1] == 0:
        S[i+1] = S[i]
water = 100*A
sugar = 0
for i in range(1, F+1):
    if W[i] and S[W[i]]/i > sugar/water:
        sugar, water = S[W[i]], i
print(sugar+water, sugar)
N,K=map(int,input().split())
print(K*((K-1)**(N-1)))

### FIXED CODE ###

a,b,c = map(int,input().split())
if(a==b and b==c):
  print(1)
elif( a!=b and b!=c and c!=a):
  print(3)
else:
  print(2)
n = int(input())

print(N * 800 - N // 15 * 200)

### FIXED CODE ###

n = int(input())

print(n * 800 - (n // 15) * 200)
n = input()
#lol=[int(n) for n in input().split()]
print(1000-(n%1000))

### FIXED CODE ###

n = int(input())
if(n%1000 ==0):
    print(0)
else:    
    ans = 1000-(n%1000)
    print(ans)
a,b,c = map(int,input().split())

if a[-1] == b[0] and b[-1] == c[0]:
  print("YES")
  return
else:
  print("NO")
  return

### FIXED CODE ###

a,b,c = input().split()

if a[-1] == b[0] and b[-1] == c[0]:
  print("YES")
else:
  print("NO")
al = "abcdefghijklmnopqrstuvwxyz"
S1 = set(sorted(input()))
if (len(all)==26):
    print("None")
else:
    for i in range (len(S1)):
        if al[i] != S1[i]:
            print(al[i])
            break

### FIXED CODE ###

al = "abcdefghijklmnopqrstuvwxyz"
S1 = sorted(list(set(input())))
if (len(S1)==26):
    print("None")
else:
    for i in range (len(S1)):
        if al[i] != S1[i]:
            print(al[i])
            break
        elif i == len(S1)-1:
            print(al[len(S1)])
            break
S = input()
N = int(input())

for i in range(min(N,K)):
    if S[i] != "1":
        print(S[i])
        quit()

print(1)

### FIXED CODE ###

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

for i in range(min(N,len(S))):
    if S[i] != "1":
        print(S[i])
        quit()

print(1)
import sys
N, M = (int(i) for i in input().split())
X = [int(i) for i in input().split()]
X.sort()

pos = [[0] * 2 for i in range(N)]
total = 0

if N > M:
    print(0)
    sys.exit()

for i in range(N):
    pos[i][0] = i
    pos[i][1] = abs(X[i+1] - X[i])
    total = total + abs(X[i+1] - X[i])


for j in range(N, M-1):
    total = total + abs(X[j+1]-X[j])
    pos = sorted(pos, key=lambda x:(x[1]))
    if pos[0][1] < abs(X[j+1]-X[j]):
        pos[0][0] = j
        pos[0][1] = abs(X[j+1]-X[j])



pos = sorted(pos, key=lambda x:(x[1]), reverse = True)
for i in range(N-1):
    total = total - pos[i][1]

print(total)


### FIXED CODE ###

import sys
N, M = (int(i) for i in input().split())
X = [int(i) for i in input().split()]
X.sort()

L = []

for i in range(1, M):
    L.append(X[i]-X[i-1])

L = sorted(L, reverse=True)

print(X[M-1]-X[0]-sum(L[:N-1]))
#wrong sample.
a,b,c,d=map(int,input().split())
mod=998244353
f=[1]
for i in range(10000):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
dp=[(d+1)*[0]for _ in range(c+1)]
dp[a][b]=1
def dfs(x,y):
  if dp[x][y]!=0:return dp[x][y]
  if x!=a and y!=b:
    ans=(dfs(x-1,y-1)*comb(x+y-1,2))%mod
    if (x-a)+(y-b)-1>=2:
      ans=(ans+comb(x-a+y-b-1,2))%mod
  elif x!=a:
    ans=(dfs(x-1,y)*y)%mod
  elif y!=b:
    ans=(dfs(x,y-1)*x)%mod
  else:
    ans=1
  dp[x][y]=ans
  return ans
print(dfs(c,d))
#for i in dp:print(i)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+1)*[0]for _ in range(c+1)]
for i in range(a,c+1):
  for j in range(b,d+1):
    if i==a and j==b:
      dp[i][j]=1
      continue
    if i==a:
      dp[i][j]=dp[i][j-1]*i%mod
      continue
    if j==b:
      dp[i][j]=dp[i-1][j]*j%mod
      continue
    dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1))%mod
print(dp[c][d])
cards = []
symbol = ['S', 'H', 'C', 'D']
for sym in symbol:
    for i in range(1, 14):
        cards.append(sym + '' + str(i))

n = int(input())
for i in range(n):
    cards.remove(input())

for card in cards:
    print(card)


### FIXED CODE ###

n = int(input())
card =[i+" "+str(j) for i in ["S","H","C","D"] for j in range(1,14)]
for i in range(n):
    card.remove(input())
for i in card:
    print(i)
#from operator import mul
#from functools import reduce
#cnt = 1000000000000000000
ans =1
N = int(input())
nums = list(map(int, input().split()))

if 0 in nums:
        print(0)
        exit()
for num in nums:
    ans *= num
    if ans > 10**18 :
        print(-1)
         exit()
print(ans)

### FIXED CODE ###

#from operator import mul
#from functools import reduce
#cnt = 1000000000000000000
ans =1
N = int(input())
nums = list(map(int, input().split()))

if 0 in nums:
        print(0)
        exit()
for num in nums:
    ans *= num
    if ans > 10**18 :
        print(-1)
        exit()
print(ans)
n = int(raw_input())

for i in range(0,n);
    a = int(raw_input())
    b = int(raw_input())
    ans = str(a+b)

    if len(ans) > 80;
        print 'overflow'
    else:
        print sum  

### FIXED CODE ###

n = int(raw_input())

for i in range(0,n):
    a = int(raw_input())
    b = int(raw_input())
    ans = str(a+b)

    if len(ans) > 80:
        print 'overflow'
    else:
        print ans
#dp[i][j]:S[i-x:i]==S[j-x:j]となる最大のx
import numpy as np

def solve(NS):
    N = NS[0]
    S = NS[1:]
    dp=np.zeros((N+1,N+1),dtype=int)
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
    return dp.max()

def main():
    NS = np.array([int(input())] + [ord(_) for _ in input()])
    print(solve(NS))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', 'i8(i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()


### FIXED CODE ###

S = input()
if S == 'Sunny':
    print('Cloudy')
elif S == 'Cloudy':
    print('Rainy')
else:
    print('Sunny')
data = int(input().split())

print((data[0]+data[1])*data[2]/2)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())

area = (a+b)*h/2
print(int(area))
N,A,B=map(int,input().split())
ballb=[]
ballr=[]
ballb.append('b')
ballb=ballb*A
ballr.append('r')
ballr=ballr*B
ball=(ballb+ballr)*N
count=0
for i in range(0,N):
    if ball[i]=='b':
        count+=1
print(count)


### FIXED CODE ###

N,A,B=map(int,input().split())
a=N//(A+B)*A
c=N%(A+B)
b=min(A,c)
print(a+b)
def main():
    N, K, S = list(map(int, input().split()))

    arr = [] 
    for i in range(0, K):
        arr += [S]
    while len(arr) < N:
        arr += [S+1]
	print(len(arr))
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K, S = list(map(int, input().split()))

    salt = -1 if S >= 10**9 else 1
    if K == 0:
        arr = [S+salt] *N
    else:
        arr = [] 
        for i in range(0, K):
            arr += [S]
        while len(arr) < N:
                arr += [S+salt]

    print(' '.join(map(str,arr)))

if __name__ == "__main__":
    main()
from math import gcd


def get_fact(n):
    arr = []
    a_append = arr.append
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1) + 1)):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            a_append([i, cnt])

    if temp != 1:
        a_append([temp, 1])

    if not arr:
        a_append([n, 1])

    return arr


# input
A, B = map(int, input().split())

# check

# ①最大公約数の素因数分解を求める
g = gcd(A, B)
fact = [f[0] for f in get_fact(g)]

# ②指数を省き、カウントする
elem = [1]
e_append = elem.append
for f in fact:
    if f not in elem:
        e_append(f)

print(elem)

print(len(elem))

### FIXED CODE ###

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    z = None
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        return z


# 引用：https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
def get_fact(n):
    arr = []
    a_append = arr.append
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1) + 1)):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            a_append([i, cnt])

    if temp != 1:
        a_append([temp, 1])

    if not arr:
        a_append([n, 1])

    return arr


# input
A, B = map(int, input().split())

# check
# 参考：https://drken1215.hatenablog.com/entry/2019/10/03/175800
# ①最大公約数の素因数分解を求める
g = gcd(A, B)
fact = [f[0] for f in get_fact(g)]

# ②指数を省き、カウントする(1は確実にあるので予めカウントしておく)
elem = [1]
e_append = elem.append
for f in fact:
    if f not in elem:
        e_append(f)

print(len(elem))
s = list(input())
n = len(s)
k = ['R','U','D']
g = ['L','U','D']

for i in range(n):
    if i % 2 ==0:
       new =[s[i] in k]
    else:
        new1 =[s[i] in g]
       
if new == [True] and new1 == [True]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = list(input())
n = len(s)
k = ['R','U','D']
g = ['L','U','D']
count =0

for i in range(n):
    if i % 2 ==0:
        if s[i] in k:
            count +=1
    else:
        if s[i] in g:
            count += 1
       
if count == n:
    print("Yes")
else:
    print("No")
if input()=='1':
    print('Hello World')
else input()=='2':
    A=int(input())
    B=int(input())
    print(A+B)

### FIXED CODE ###

N = int(input())
if N==1:
    print('Hello World')
else:
    A=int(input())
    B=int(input())
    print(A + B)
import sys

n,k = list(map(int, input().split()))
l = list(map(int, input().split()))
dp = [sys.maxsize]*n
dp[0]=0
# for i in range(1,n):
#     for j in range(1,k+1):
#         if i-j>=0:
#             dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
dp[1] = abs(l[1]-l[0])
for i in range(2,n):
    if i-j>=0:
        dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
print(dp[n-1])

### FIXED CODE ###

import sys

n,k = list(map(int, input().split()))
l = list(map(int, input().split()))
dp = [sys.maxsize]*n
dp[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))   
print(dp[n-1])
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y1,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=map(int,input().split())
  print(max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]))
if'__main__'==__name__:s()


### FIXED CODE ###

def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):
   P[i+1][1:-1]=map(int,input().split())
  a=0
  for i in range(1,m+1):
   for j in range(1,n+1):
    if P[i][j]:
     t=b(P,i,j)
     if a<t:a=t
  print(a)
if'__main__'==__name__:s()
h,w = map(int, input().split())
listA = [input() for i in range(h)]
for i in range(h):
  print(listA[i-1]"\n"listA[i-1])


### FIXED CODE ###

h,w = map(int, input().split())
listA = [input() for i in range(h)]
for i in range(h):
  print(listA[i]+"\n"+listA[i])
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

if S[0] == S[1] == S[2]:
    print("No")
    exit()
print("Yes")

### FIXED CODE ###

#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

if S[0] == S[1] == S[2]:
    print("No")
    exit()
print("Yes")
work = [[[] for j in range(w)] for i in range(h)]
result = 0
for i in range(h):
    for j in range(w):
        append = work[i][j].append
        if i<h-1 and s[i+1][j] == ".":
            append([i+1,j])
        if i>0 and s[i-1][j] == ".":
            append([i-1,j])
        if j<w-1 and s[i][j+1] == ".":
            append([i,j+1])
        if j>0 and s[i][j-1] == ".":
            append([i,j-1])
for i in range(h):
    for j in range(w):
        if s[i][j] != ".":
            continue
        q = deque([[i, j]])
        temp = [[i, j]]
        popleft = q.popleft
        append = q.append
        d = -1
        count = 1
        counter = 0
        for k in range(h*w):
            x, y = popleft()
            count -= 1
            for el in work[x][y]:
                if el not in temp:
                    counter += 1
                    append(el)
                    temp.append(el)
            if count == 0:
                d += 1
                count = counter
                counter = 0
            if len(q) == 0:
                break
        result = result if result>d else d
print(result)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
work = [[[] for j in range(w)] for i in range(h)]
result = 0
for i in range(h):
    for j in range(w):
        append = work[i][j].append
        if i<h-1 and s[i+1][j] == ".":
            append([i+1,j])
        if i>0 and s[i-1][j] == ".":
            append([i-1,j])
        if j<w-1 and s[i][j+1] == ".":
            append([i,j+1])
        if j>0 and s[i][j-1] == ".":
            append([i,j-1])
q = deque()
popleft = q.popleft
append = q.append
for i in range(h):
    for j in range(w):
        if s[i][j] != ".":
            continue
        q.clear()
        q.append([i, j])
        temp = [[i, j]]
        tempappend = temp.append
        d = -1
        count = 1
        counter = 0
        for k in range(w*h):
            x, y = popleft()
            count -= 1
            for el in work[x][y]:
                if el not in temp:
                    counter += 1
                    append(el)
                    tempappend(el)
            if count == 0:
                d += 1
                count = counter
                counter = 0
            if len(q) == 0:
                break
        result = result if result>d else d
    if result == h+w-2:
        break
print(result)
s = input()
c = ''
for t in s:
  if t == '0' or t == '1':
    c += t
  if t == 'B' and c != '':
    c -= c[-1]
print(c)


### FIXED CODE ###

s = input()
l = []
for t in s:
  if t == '0' or t == '1':
    l.append(t)
  elif t == 'B':
    if l != []:
      l.pop()
for r in l:
  print(r, end='')
# -*- coding:utf-8 -*-
import sys

def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if 0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym:
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1, 0, 1, 0]
DY = [0, -1, 0, 1]
sys.setrecursionlimit(10000000)
tile = [[0 for i in range(1)] for j in range(1)]
while True:
	counter+=1
	line = input()
	if ' ' in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(N)] for j in range(M)]
	if N is 0 and M is 0:
		break
	else:
		tile[counter-2] = list(line)
	if (counter-1)==M:
		solve()
		counter = 0

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0
import numpy as np

n = int(input())
x = [tuple(map(int, input().split())) for _ in range(n)]

def circle(x, y, z):

    ra = np.array(x)
    rb = np.array(y)
    rc = np.array(z)

    A = np.dot(rb-rc,rb-rc)
    B = np.dot(rc-ra,rc-ra)
    C = np.dot(ra-rb,ra-rb)

    T = A*(B+C-A)
    U = B*(C+A-B)
    W = C*(A+B-C)

    rcc = (T*ra + U*rb + W*rc)/(T + U + W)

    return rcc

def dis(a, b, c, d):
    return (a - b)**2 + (c - d)**2

e = 10 ** (-9)
ans = 10 ** 18
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            a = x[i]
            b = x[j]
            c = x[k]
            px, py = circle(a, b, c)
            r = dis(px, a[0], py, a[1])
            ok = True
            for s, t in x:
                if dis(px, s, py, t) > r + e:
                    ok = False
                    break
            if ok:
                ans = min(ans, r)
for i in range(n):
    for j in range(i+1, n):
        a = x[i]
        b = x[j]
        px, py = (a[0]+b[0])/2, (a[1]+b[1])/2
        r = dis(px, a[0], py, a[1])
        ok = True
        for s, t in x:
            if dis(px, s, py, t) > r + e:
                ok = False
                break
        if ok:
            ans = min(ans, r)

print(ans ** (1/2))

### FIXED CODE ###

import numpy as np

n = int(input())
x = [tuple(map(int, input().split())) for _ in range(n)]

def circle(x, y, z):

    ra = np.array(x)
    rb = np.array(y)
    rc = np.array(z)

    A = np.dot(rb-rc,rb-rc)
    B = np.dot(rc-ra,rc-ra)
    C = np.dot(ra-rb,ra-rb)

    T = A*(B+C-A)
    U = B*(C+A-B)
    W = C*(A+B-C)

    rcc = (T*ra + U*rb + W*rc)/(T + U + W)

    return rcc

def dis(a, b, c, d):
    return (a - b)**2 + (c - d)**2

e = 10 ** (-9)
ans = 10 ** 18
for i in range(n):
    for j in range(i+1, n):
        a = x[i]
        b = x[j]
        px, py = (a[0]+b[0])/2, (a[1]+b[1])/2
        r = dis(px, a[0], py, a[1])
        ok = True
        for s, t in x:
            if dis(px, s, py, t) > r + e:
                ok = False
                break
        if ok:
            ans = min(ans, r)

if ans != 10 ** 18:
    print(ans ** (1/2))
    exit()

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            a = x[i]
            b = x[j]
            c = x[k]
            px, py = circle(a, b, c)
            r = dis(px, a[0], py, a[1])
            ok = True
            for s, t in x:
                if dis(px, s, py, t) > r + e:
                    ok = False
                    break
            if ok:
                ans = min(ans, r)

print(ans ** (1/2))
# ABC 137 E    E. Coins Respawn

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！



def BELLMANFORD(point,d,p):
    cost       = [-float("inf")]*(n+1)  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*(n+1)                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now]==1:
                    negative[nex]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now]=1
 
    return cost,negative

def main():
    
    n,m,p=map(int,input().split())

    d={}
    for s in range(m):
        a,b,c=map(int,input().split())
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


n,m,p=map(int,input().split())

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]

#print(d)


def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()