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

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

light = [[[0, 0, 0, 0] for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = light[h][w]
            if h + 1 < H and grid[h + 1][w] == '.':
                light[h + 1][w][1] = here[1] + 1
            if w + 1 < W and grid[h][w + 1] == '.':
                light[h][w + 1][3] = here[3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = light[h][w]
            if h - 1 >= 0 and grid[h - 1][w] == '.':
                light[h - 1][w][0] = here[0] + 1
            if w - 1 >= 0 and grid[h][w - 1] == '.':
                light[h][w - 1][2] = here[2] + 1
            ans = max(ans, sum(here) + 1)

print(ans)


### FIXED CODE ###

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

light = [0] * 4 * (W + 1) * (H + 1)

row = 4 * (W + 1)
col = 4

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h + 1) + col * w + 1] = light[here + 1] + 1
            light[row * h + col * (w + 1) + 3] = light[here + 3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h - 1) + col * w + 0] = light[here + 0] + 1
            light[row * h + col * (w - 1) + 2] = light[here + 2] + 1
            ans = max(ans, sum(light[here: here + 4]) + 1)

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

s=input()

i=0
cnt=0
while(True):
    if len(s)<2 or i+1>=len(s):
        break
    if s[i]!=s[i+1]:
        cnt+=1
        s=s[:i]+s[i+2:]
        i=0
    else:
        i+=1
print(cnt*2)
        

### FIXED CODE ###

s=input()
cnt_0=0
cnt_1=0
for i in range(len(s)):
    if s[i]=="0":
        cnt_0+=1 
    else:
        cnt_1+=1
        
    
print(min(cnt_0,cnt_1)*2)
### BUGGY CODE ###

import math

def f(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))

n, a, b = map(int, input().split())

ans = pow(2, n) - 1
ans = ans - f(n, a) - f(n, b)
ans %= ((10**9)+7)
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())

MOD = 10**9 + 7
x = 1
y = 1
ans = pow(2, n, MOD) - 1

for i in range(1, b+1):
    x = x * i % MOD
    y = y * (n-i+1) % MOD
    if i == a or i == b:
        ans -= y * pow(x, MOD-2, MOD)

print(ans%MOD)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
ans = 0
for i in range(n-2):
    a = l[i]
    x = i
    for j in range(i+1,n-1):
        b = l[j]
        y = j
        for k in range(j+1,n):
            if x == k or y == k:
                continue
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = l[i]
        b = l[j]
        x = (a+1) - b
        y = (b+1) - a
        z = max(x,y)
        a = j+1
        b = n-1
        c = (a+b) // 2
        while a <= b:
            if l[c] == z:
                a += 1
            elif l[c] > z:
                a = c + 1
            elif l[c] < z:
                b = c - 1
            else:
                pass
            c = (a+b) // 2
        ans += c-j
print(ans)
### BUGGY CODE ###

import numpy as np
from numba import njit

n, k = map(int, input().split())
MOD = 998244353

lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr += (list(range(l, r + 1)))

lr.sort()
lr = np.array(lr)

dp = np.zeros(n + n, dtype=np.int64)
dp[0] = 1
dp2 = dp.copy()


@njit(cache=True)
def solve(n, lr, dp, dp2):
    for i in range(n):
        idx = i + lr
        dp2[idx] += dp[i]
        dp2 %= MOD
        dp = dp2
    return dp[n - 1]


print(solve(n, lr, dp, dp2))

### FIXED CODE ###

def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
MOD = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque([[i,j]])
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append([hh+k,ww+l])

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()
    


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j ))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] <= dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

anss = 0
for i in range(h+2):
    for j in range(w+2):
        if A[i][j] == "#":
            continue
        anss = max(anss,bfs(i,j))
print(anss)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split())) 
ans = 1

for i in range(n):
  ans *= a[i]
  
if ans > 1000000000000000000:
  print('-1')
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split())) 
ans = 1

if 0 in a:
  print(0)

else:
  for i in range(n):
    ans *= a[i]
    if ans > 10**18:
      print(-1)
      exit()
  print(ans)
### BUGGY CODE ###

n = int(input())
pw = 1

for i in range(n):
    pw *= i+1
    
print(pw%(10**9+7))

### FIXED CODE ###

import math

n = int(input())

pw = math.factorial(n)
    
print(pw%(10**9+7))
### BUGGY CODE ###

nk = input().split()
n = int(nk[0])
k = int(nk[1])
alist = [int(a) for a in input().split()]


bit_count = [{0: 0, 1: 0} for i in range(42)]
for i in range(42):
    for a in alist:
        b = a >> i
        b %= 2
        which = 0 if b == 1 else 1
        bit_count[i][which] += 1


def calc_pow_multiple(digit, selected):
    count = bit_count[digit][selected]
    ret = 1<<digit
    ret *= count
    return ret


def calc_maxsum(kk, digit):
    if digit < 0:
        return 0

    kkbit = kk >> digit
    kkbit %= 2

    if kkbit == 0:
        return calc_pow_multiple(digit, 0) + calc_maxsum(kk, digit - 1)

    sum_0 = calc_pow_multiple(digit, 0) + calc_maxsum((1<<digit) - 1, digit - 1)
    sum_1 = calc_pow_multiple(digit, 1) + calc_maxsum(kk, digit - 1)
    return max(sum_0, sum_1)


print(calc_maxsum(k, 41))


### FIXED CODE ###

nk = input().split()
n = int(nk[0])
k = int(nk[1])
alist = [int(a) for a in input().split()]


bit_count = [{0: 0, 1: 0} for i in range(42)]
for i in range(42):
    for a in alist:
        b = a >> i
        b &= 1
        which = 0 if b == 1 else 1
        bit_count[i][which] += 1


def calc_pow_multiple(digit, selected):
    count = bit_count[digit][selected]
    ret = 1<<digit
    ret *= count
    return ret


def calc_maxsum(kk, digit):
    if digit < 0:
        return 0
    if kk == (1<<(digit + 1)) - 1:
        partsum_0 = calc_pow_multiple(digit, 0)
        partsum_1 = calc_pow_multiple(digit, 1)
        return max(partsum_0, partsum_1) + calc_maxsum(kk>>1, digit - 1)

    kkbit = kk >> digit
    kkbit &= 1

    if kkbit == 0:
        return calc_pow_multiple(digit, 0) + calc_maxsum(kk, digit - 1)

    sum_0 = calc_pow_multiple(digit, 0) + calc_maxsum((1<<digit) - 1, digit - 1)
    sum_1 = calc_pow_multiple(digit, 1) + calc_maxsum(kk, digit - 1)
    return max(sum_0, sum_1)


print(calc_maxsum(k, 41))
### BUGGY CODE ###

n, p = map(int, input().split())
if n == 1 or p== 1:
    print(p)
    exit()
c2 = 0
while p%2 == 0:
    c2 += 1
    p//=2
c = 2**(c2//n)
max = 1
i = 1
while i**n <= p:
    i *= 2
while i > 1:
    if p%(i**n) == 0:
        print(c*i)
        exit()
    else:
        i -= 1
print(c)


### FIXED CODE ###

n, p = map(int, input().split())
if n == 1 or p== 1:
    print(p)
    exit()
c2 = 0
while p%2 == 0:
    c2 += 1
    p//=2
c = 2**(c2//n)
i = int(p**(1/n))+1
if i%2 == 0:
    i -= 1
while i > 1:
    if p%(i**n) == 0:
        print(c*i)
        exit()
    else:
        i -= 2
print(c)
### BUGGY CODE ###

#辞書でデータを持たずに、配列のindexに対応して値を持ったほうが良い
#例）
#dic={}
#dic[1]=[1,2]
#hairetsu =[]*n
#hairetsu[1]=[1,2]
#大きい数字はMLEやTLEにつながる

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

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

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

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

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")
### BUGGY CODE ###

k,n=map(int,input().split())
home = input()
home = home.split()
for i in range(len(home)):
    home[i] = int(home[i])

def search(i,home,l):
    d = 0
    leng = len(home)
    count=0
    while True:
        if count==leng-1:
            break
        j=i+1
        if j==leng:
            d+=home[0]+k-home[i]
            count+=1
            continue
        d += home[i+1]-home[i]
        count+=1
        i+=1
        if i == leng:
            i=0
    d2=0
    while True:
        if count==leng-1:
            break
        j=i-1
        if j==-1:
            d2+=home[leng-1]-home[0]+k
            count+=1
            continue
        d2 += home[i-1]-home[i]
        count+=1
        i+=1
        if i == -1:
            i=leng-1
    if d<=d2:
        l.append(d2)
    else:
        l.append(d)
    return
        


l=[]
for i in range(len(home)):
    search(i,home,l)
print(min(l))
    

### FIXED CODE ###

k,n=map(int,input().split())
home = input()
home = home.split()
for i in range(len(home)):
    home[i] = int(home[i])
d=[]
for i in range(len(home)):
    if i == len(home)-1:
        d.append(home[0]+k-home[i])
        break
    d.append(home[i+1]-home[i])
Max = max(d)
leng=len(home)
count=0
for i in range(len(d)):
    if d[i] == Max:
        break
d=0
while True:
    
    if count==leng-1:
        break
    j=i-1
    if i==0:
        d+=abs(home[leng-1]-(home[0]+k))
        count+=1
    else:
        d += abs(home[i]-home[i-1])
        count+=1
    i-=1
    if i == -1:
        i=leng-1
print(d)
### BUGGY CODE ###

N,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
dp=[0]*N
dp[0]=1
Ma=max(A)
B=[0]*(Ma+1)
B[A[0]]=1
for i in range(1,N):
    a=A[i]
    Max=max(B[max(0,a-K):min(Ma+1,a+K+1)])
    dp[i]=Max+1
    B[a]=Max+1
print(max(B))

### FIXED CODE ###

N,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

#####ide_ele#####
ide_ele =0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
Ma=max(A)
Tree=[0]*(Ma+1)
seg = SegTree(Tree, segfunc, ide_ele)
ans=0
for i in range(N):
    a=A[i]
    l=max(0,a-K)
    r=min(a+K,Ma)
    Ans=seg.query(l,r+1)
    seg.update(a, Ans+1)
    ans=max(ans,Ans+1)
print(ans)
### BUGGY CODE ###

N = int(input())
An = list(map(int, input().split()))
Bn = list(map(int, input().split()))

cnt = 0

while len(An) > 1:
    m = An.pop(0)
    y = Bn.pop(0)
    n = An[0]
    if y < m:
        cnt += y
    elif m <= y < m+n:
        cnt += y
        An[0] -= y-m
    else:
        cnt += m+n
        An[0] = 0
    #print(cnt)
    #print(An)
    #print(Bn)

print(cnt)
    


### FIXED CODE ###

from collections import deque

N = int(input())
An = deque(map(int, input().split()))
Bn = deque(map(int, input().split()))

cnt = 0

while len(An) > 1:
    m = An.popleft()
    y = Bn.popleft()
    n = An[0]
    if y < m:
        cnt += y
    elif m <= y < m+n:
        cnt += y
        An[0] -= y-m
    else:
        cnt += m+n
        An[0] = 0
    #print(cnt)
    #print(An)
    #print(Bn)

print(cnt)
### BUGGY CODE ###

n = input()
count = 0
for i in xrange(n):
    x = input()
    if x == 2: count += 1
    elif x % 2 != 0:
        for j in xrange(3,int(x*0.5+1),2):
            if x % j == 0: break
        else: count += 1
print count

### FIXED CODE ###

import math
def prime(x):
    if x == 2: return True
    elif x % 2 == 0: return False
    else:
        for j in xrange(3,int(math.sqrt(x))+1,2):
            if x % j == 0: return False
        else:
            return True 
n = input()
count = 0
for i in xrange(n):
    if prime(input()): count += 1
print count
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

jun = []
# O(2n)
def chil_pop(l,p):
    jun.append(l)
    for i in b[l]:
        if i == p:
            continue
        chil_pop(i,l)
    b[l] = p

chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x

for i in jun[1:]:
    ans[i] += ans[b[i]]

ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

for i in range(1, n + 1):
    count = a.count(i)
    del a[:count]
    print(count)



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
lst = [0] * n
for i in a:
    lst[i-1] += 1
print(*lst)
### BUGGY CODE ###

import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    S = int(input())
    mod = (10 ** 9 + 7)

    if S < 3:
        print(0)
        exit()

    inf = S // 3 +3 # 最大桁数
    sup = (S-1)//9



    ans =0

    dp= [0]*(S+1)
    dp[0] =1


    for i in range(inf):
        for j in range(S,-1,-1):
            dp[j] = sum( dp[0:max(j-2,0)])
            dp[j] %=mod

        ans +=dp[S]
        ans %=mod


    print(ans)






if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    S = int(input())
    mod = (10 ** 9 + 7)

    if S < 3:
        print(0)
        exit()

    inf = S // 3 +3 # 最大桁数
    sup = (S-1)//9



    ans =0

    dp= [0]*(S+1)
    dp[0] =1


    for i in range(inf):
        for j in range(S,-1,-1):
            if j ==S:
                dp[j] = sum(dp[0:max(j - 2, 0)])
            else:
                if j>=3:
                    dp[j] = dp[j+1] - dp[j-2]
                else:
                    dp[j]=0
            dp[j] %=mod

        ans +=dp[S]
        ans %=mod


    print(ans)






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

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
B = [0] * M
C = [0] * M
for i in range(M):
    B[i], C[i] = [int(i) for i in input().strip().split()]

A.sort()
for i in range(M):
    for j in range(B[i]):
        if A[j] < C[i]:
            A[j] = C[i]
    A.sort()
print(sum(A))


### FIXED CODE ###

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A.sort()

BC = [[0, 0] for _ in range(M)]
for j in range(M):
    BC[j][0], BC[j][1] = [int(i) for i in input().strip().split()]
BC.sort(key=lambda x: x[1])

res = 0
cnt = 0
i = N - 1
j = M - 1
while True:
    if cnt == N:
        break

    if j == -1:
        res += A[i]
        i -= 1
    elif A[i] > BC[j][1]:
        res += A[i]
        i -= 1
    elif A[i] <= BC[j][1]:
        res += BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j -= 1
    else:
        raise ValueError
    cnt += 1
print(res)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    edge = []
    g = [[] for _ in range(N)]
    rg = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge.append((A,B,C))
        g[A].append(B)
        rg[B].append(A)

    
    visited = [False] * N
    rvisited = [False] * N
    Q = deque()
    Q.append(0)
    while Q:
        v = Q.popleft()
        visited[v] = True
        for i in g[v]:
            if not visited[i]:
                Q.append(i)

    Q.append(N-1)
    while Q:
        v = Q.popleft()
        rvisited[v] = True
        for i in rg[v]:
            if not rvisited[i]:
                Q.append(i)
    
    OK = [False] * N
    for i in range(N):
        OK[i] = visited[i] & rvisited[i]
    
    flag = True
    d = [float('inf')] * N
    d[0] = 0
    step = 0
    while flag:
        flag = False
        for A, B, C in edge:
            if not OK[A]:
                continue
            if not OK[B]:
                continue
            newD = d[A] + C
            if newD < d[B]:
                d[B] = newD
                flag = True
        step += 1
        if step > N:
            print(-1)
            exit()

    print(max(0,-d[N-1]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M, P = map(int, input().split())
    edge = [[] for _ in range(N)]
    redge = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge[A].append((B,C))
        redge[B].append(A)

    # 0 => N-1の間にある閉路を検出したいので
    # 0とN-1からたどりつけない場所は前処理で取り除く
    
    visited1, visited2 = {0}, {N-1}
    
    stack = [0]
    while stack:
        v = stack.pop()
        for dest, _ in edge[v]:
            if dest in visited1:
                continue
            visited1.add(dest)
            stack.append(dest)
    
    stack = [N-1]
    while stack:
        v = stack.pop()
        for dest in redge[v]:
            if dest in visited2:
                continue
            visited2.add(dest)
            stack.append(dest)
    
    OK = visited1 & visited2
    
    new_edge = [[] for _ in range(N)]
    for s in range(N):
        for t, c in edge[s]:
            if t in OK:
                new_edge[s].append((t,c))

    flag = True
    d = [float('inf')] * N
    d[0] = 0
    #ベルマンフォード法、N回実行してまだ更新されている場合は負の閉路が存在する
    for _ in range(N):
        flag = False
        for v, e in enumerate(new_edge):
            for t, c in e:
                if d[v] != float('inf') and d[v] + c < d[t]:
                    d[t] = d[v] + c
                    flag = True
        if not flag:
            print(max(0,-d[N-1]))
            exit()
    else:
        print(-1)
        exit()


if __name__ == "__main__":
    main()