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

from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = [((0, 0), x1-1, y1-1, i) for i in range(4)]
for i in range(4):
    dp[x1-1][y1-1][i] = (0, 0)

while q:
    count, x, y, d = heappop(q)
    if count != dp[x][y][d]:
        continue

    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] < nextcount:
                continue
            dp[x+dx][y+dy][dd] = nextcount
            heappush(q, (nextcount, x+dx, y+dy, dd))

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
print(ans)


### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])
### BUGGY CODE ###

n,m=map(int,input().split())
prev=[];ord=[[]for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  prev.append([a,b])
  ord[a].append(b)
for i in range(n+1):
  ord[i]=sorted(ord[i])
for p in prev:
  x,y=p[0],p[1]
  ind=ord[x].index(y)+1
  print("%06d"%x+"%06d"%ind)

### FIXED CODE ###

n,m=map(int,input().split());li=[]
for i in range(m):
  li.append(list(map(int,input().split()))+[i])
li.sort()
cac=li[0][0];o=2
li[0][1]=1
for g in li[1:]:
  if g[0]!=cac:
    cac=g[0]
    o=1
  g[1]=o
  o+=1
li.sort(key=lambda x:x[-1])
for g in li:
  print("%06d"%g[0]+"%06d"%g[1])
### BUGGY CODE ###

import bisect

n = int(input())
a_li = list(map(int, input().split()))
b_li = list(map(int, input().split()))
c_li = list(map(int, input().split()))

b_li.sort()
c_li.sort()

ans = 0

for i in a_li:
    s = bisect.bisect(b_li, i)
    
    for j in b_li[s:]:
        t = bisect.bisect(c_li, j)
        ans += n-t
        
print(ans)

### FIXED CODE ###

import bisect

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

a.sort()
b.sort()
c.sort()

ans = 0

for middle in b:
    tmp1 = bisect.bisect_left(a, middle)
    tmp2 = bisect.bisect_right(c, middle)
    ans += tmp1 * (n - tmp2)

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

N = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(N):
    dic[a.index(a[i])+1] = a[i]
dic_sorted = sorted(dic.items(), key=lambda x:x[1])
for i in range(N):
    print(dic_sorted[i][0],'',end="")

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(N):
    dic[i+1] = a[i]
dic_sorted = sorted(dic.items(), key=lambda x:x[1])
for i in range(N):
    print(dic_sorted[i][0],'',end="")
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[22]:


N,Q = map(int, input().split())
S = str(input())
#data = []
#for i in range(Q):
#    data.append(list(map(int, input().split())))
data = []
for i in range(Q):
    data= list(map(int, input().split()))
    print(S[data[0]-1:data[1]].count("AC"))


# In[23]:


#for j in range(Q):
#    print(S[data[j][0]-1:data[j][1]].count("AC"))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[15]:


N,Q = map(int, input().split())
S = list(input())
mylist = [0]
cnt = 0
for i in range(1,len(S)):
    if S[i-1] == "A" and S[i] == "C":
        cnt += 1
    mylist.append(cnt)
for _ in range(Q):
    l,r = map(int, input().split())
    ans = mylist[r-1] - mylist[l-1]
    print(ans)


# In[ ]:
### BUGGY CODE ###

#coding: utf-8
def main(N, K, h):
    #N, K = map(int, input().split())
    #h = list(map(int, input().split()))
    dp = [float("inf") for _ in range(N)]
    dp[0] = 0
    for i in range(1, N):
        M = i if i <= K else K
        dp[i] = min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, M+1)])
        #dp[i] = min(a)
        #for k in range(1, M+1):
         #   dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)

### FIXED CODE ###

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)
### BUGGY CODE ###

l, r = [int(e) for e in input().split()]
m = 2019
for i in range(l, r):
  ir = i % 2019
  for j in range(i + 1, r + 1):
    t = (ir * j) % 2019
    if t < m:
      m = t
print(m)

### FIXED CODE ###

l, r = [int(e) for e in input().split()]
m = 2019
for i in range(l, r):
  ir = i % 2019
  for j in range(i + 1, r + 1):
    t = (ir * j) % 2019
    if t < m:
      m = t
    if m == 0:
      break
  if m == 0:
    break
print(m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
def inp():
    return map(int,input().split())
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = inp()
    e[a-1].append(b-1)
    e[b-1].append(a-1)

p = [0] * n
for _ in range(q):
    pp, x = inp()
    p[pp - 1] += x


def dfs(i=0, r=-1):
    for j in e[i]:
        if j != r:
            p[j] += p[i]
            dfs(j, i)
dfs()

print(*p)


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
### BUGGY CODE ###

H, W = map(int, input().split())
func = (lambda x: 1 if x == "#" else 0)
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ

print(ans)



### FIXED CODE ###

H, W = map(int, input().split())
func = (lambda x: 1 if x == "#" else 0)
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ

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

import numpy as np
import math

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A)

for i in range(M):
    j = A.argmax()
    A[j]  =  math.floor(A[j] / 2)

print(A.sum())


### FIXED CODE ###

import numpy as np
import math
import heapq

N, M = map(int, input().split())
A = list(map(lambda x: [-int(x),int(x)], input().split()))
heapq.heapify(A)

for i in range(M):
    x = heapq.heappop(A)
    x[1] //= 2
    x[0] = -x[1]
    heapq.heappush(A, x)

ans = 0
for i in range(N):
    ans += A[i][1]
print(ans)
### BUGGY CODE ###

def main():
    import numpy as np
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shop_a = []
    shop_b = []
    shopsA0 = []

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b+1)
        else:
            shop_a.append(a)
            shop_b.append(b)
    
    shopsA0.sort()

    shop_a = np.array(shop_a, dtype=np.int64)
    shop_b = np.array(shop_b, dtype=np.int64)
    key = shop_a / (shop_b+1)
    sort_index = np.argsort(key)[::-1]
    shop_a = shop_a[sort_index]
    shop_b = shop_b[sort_index]

    DP = np.full(29, t+10, dtype=np.int64)
    DP[0] = 0

    for a, b in zip(shop_a, shop_b):
        np.minimum(DP[1:], (DP[:-1] + 1) * (a + 1) + b, out=DP[1:])

    cumA0 = np.cumsum(shopsA0, dtype=np.int64)

    DP = DP[DP <= t]
    DPA0 = np.searchsorted(cumA0, t - DP, side='right')
    ans = np.arange(len(DP)) + DPA0
    print(ans.max())


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = [0]

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b + 1)
        else:
            shops.append([a / (b + 1), a, b])

    shopsA0.sort()
    shops.sort(reverse=True)


    DP = [t+10] * 30
    DP[0] = 0

    for _, a, b in shops:
        for num in range(28, -1, -1):
            candidate = (DP[num]+1) * (a+1) + b
            if candidate < DP[num+1]:
                DP[num+1] = candidate

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A0 = len(cumA0) - 1
    for count, spend_time in enumerate(DP):
        residue = t - spend_time
        if residue < 0:
            break
        while count_A0 > 0 and cumA0[count_A0] > residue:
            count_A0 -= 1
        ans.append(count_A0 + count)
    print(max(ans))


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

def minus(n):
    return n - 1

n,k,q = map(int,input().split())
a = [0] * q
b = [0] * n

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

member = [k]*n

for j in range(q):
    member[a[j]-1] = member[a[j]-1] + 1
    member = list(map(minus,member))

for k in range(n):
    if member[k] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [0] * q

member = [k] * n

for i in range(q):
    a[i] = int(input())
    member[a[i]-1] = member[a[i]-1] + 1

for j in range(n):
    if member[j] - q <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
pre = True
ans = 1
for i in range(1,n):
  if pre and p[i]<=p[i-1]:
    ans += 1
  elif not pre and p[i]>p[i-1]:
    pre = False
  else:
    if min(p[:i])>=p[i]:
      ans += 1
      pre = True
    else:
      pre = False
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
pre = True
premin = p[0]
ans = 1
for i in range(1,n):
  if pre and p[i]<=p[i-1]:
    ans += 1
    premin = p[i]
  elif not pre and p[i]>p[i-1]:
    pre = False
  else:
    if premin>=p[i]:
      ans += 1
      pre = True
      premin = p[i]
    else:
      pre = False
print(ans)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def solve():
  n = ni()
  a = nl()
  m = max(a)
  mod = 998244353
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  sieve = [1]*(m+1)
  sieve[0] = sieve[1] = 0
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(m//i, 0, -1):
        sieve[j*i] = 0
        l[j] += l[j*i]
      sieve[i] = 1
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(1, m//i + 1):
        l[j] -= l[j*i]
  s = -sum(a)
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * modinv(i, mod)) % mod
  print(s * modinv(2, mod) % mod)
  return

solve()

### FIXED CODE ###

import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def solve():
  n = ni()
  a = nl()
  m = max(a)
  mod = 998244353
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  sieve = [1]*(m+1)
  sieve[0] = sieve[1] = 0
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(m//i, 0, -1):
        sieve[j*i] = 0
        l[j] += l[j*i]
      sieve[i] = 1
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(1, m//i + 1):
        l[j] -= l[j*i]
  s = -sum(a)
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * modinv(i, mod)) % mod
  print(s * modinv(2, mod) % mod)
  return

solve()
### BUGGY CODE ###

import math
import numpy as np
from numba import jit

def main(N, K, plist, slist, max_score):
    for start in range(N):
        total_score_in_loop = 0
        now = start
        score_loop = []
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        score_rem = 0
        loop_score = 0
        for index, score in enumerate(score_loop, start=1):
            score_rem += score
            if total_score_in_loop > 0:
                loop_score = total_score_in_loop * ((K-index) // len(score_loop))
            if max_score < score_rem+loop_score:
                max_score = score_rem+loop_score
    print(max_score)

if __name__ == '__main__':
    N, K = map(int, input().split())
    plist = np.array([i - 1 for i in map(int, input().split())])
    slist = np.array(list(map(int, input().split())))
    max_score = -10**18
    main(N, K, plist, slist, max_score)

### FIXED CODE ###

import numpy as np
from numba import njit

@njit('i8(i8,i8,i8[:],i8[:],i8)', cache=True)
def main(N, K, plist, slist, max_score):
    for start in range(N):

        total_score_in_loop = 0
        score_loop = []
        now = start
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        
        rem_score, loop_score = 0, 0
        for idx in range(1, len(score_loop)+1):
            rem_score += score_loop[idx-1]
            if total_score_in_loop > 0:
                loop_score = ((K - idx) // len(score_loop)) * total_score_in_loop
            max_score = max(max_score, rem_score + loop_score)
    return max_score


N, K = map(int, input().split())
plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
slist = np.array([i for i in map(int, input().split())], dtype='int64')
max_score = -10**15
max_score = main(N, K, plist, slist, max_score)
print(max_score)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

ans = 0
combinations = list()
for j, i in enumerate(range(k - 1, n)):
    if i == (k - 1):
        combinations.append(1)
    else:
        combinations.append(combinations[-1] * i // (i - k + 1))
    # combinations[-1] = combinations[-1] % MOD
    # print(i, 'C', k - 1, '=', combinations[-1])

# print(combinations)
# print(A)
combinations = combinations[::-1]
for j, i in enumerate(range(k - 1, n)):
    ans += (A[-j - 1] * combinations[j] % MOD)

for j, i in enumerate(range(k - 1, n)):
    ans -= (A[j] * combinations[j] % MOD)
    if ans < 0:
        ans = ans + (- ans // MOD + 1) * MOD

ans %= MOD
print(ans)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7


def pow(a, n):
    if n == 0:
        return 1
    else:
        temp = pow(a, n // 2)
        if n % 2 == 0:
            return temp * temp % MOD
        else:
            return temp * temp * a % MOD
        
        
ans = 0
combinations = list()
for j, i in enumerate(range(k - 1, n)):
    if i == (k - 1):
        combinations.append(1)
    else:
        combinations.append(combinations[-1] * i * pow(i - k + 1, MOD - 2))
    combinations[-1] = combinations[-1] % MOD
    # print(i, 'C', k - 1, '=', combinations[-1])

# print(combinations)
# print(A)
combinations = combinations[::-1]
for j, i in enumerate(range(k - 1, n)):
    ans += (A[-j - 1] * combinations[j] % MOD)

for j, i in enumerate(range(k - 1, n)):
    ans -= (A[j] * combinations[j] % MOD)
    if ans < 0:
        ans = ans + (- ans // MOD + 1) * MOD

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


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

slink = []
glink = []

for i in range(M):

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

    if a == 1:
        slink.append(b)
    elif b == 1:
        slink.append(a)
    elif a == N:
        glink.append(b)
    elif b == N:
        glink.append(a)

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

print (ans)

### FIXED CODE ###


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

slink = {}
glink = {}

for i in range(M):

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

    if a == 1:
        slink[b] = 1
    elif b == 1:
        slink[a] = 1
    elif a == N:
        glink[b] = 1
    elif b == N:
        glink[a] = 1

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

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

L, R = map(int, input().split())
ij = [_ for _ in range(L, R+1)]
list_ = []
for i in ij:
    for j in ij:
        if i < j:
            list_.append((i*j) % 2019)
print(min(list_))

### FIXED CODE ###

l, r = map(int, input().split())
if r // 3 > (l - 1) // 3 and r // 673 > (l - 1) // 673:
    print(0)
else:
    print(min(i * j % 2019 for i in range(l, r + 1) for j in range(l, i)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

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

INF = 10**10
# Bellman-Fordをするときは、辺集合を持つ
edges = [] 
# 1から行けない辺やNに到達できない辺を削除するための探索をする用
to = [[] for _ in range(2505)]
rto = [[] for _ in range(2505)]
reachableFrom1 = [False for _ in range(2505)]
reachableToN = [False for _ in range(2505)]
ok = [False for _ in range(2505)]

def dfs(v):
    if reachableFrom1[v]:
        return
    reachableFrom1[v] = True
    for u in to[v]:
        dfs(u)

def rdfs(v):
    if reachableToN[v]:
        return
    reachableToN[v] = True
    for u in rto[v]:
        rdfs(u)

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    c -= P
    c = -c # 最短路にするため符号を逆転
    edges.append([a, b, c])
    to[a].append(b)
    rto[b].append(a)

# 考えるべき頂点だけ洗い出し
dfs(0)
rdfs(N-1)
for i in range(N):
    ok[i] = reachableFrom1[i] & reachableToN[i]

# Bellman-Ford
d = [INF for _ in range(N)]
d[0] = 0
upd = True
step = 0
flag = True
while upd:
    upd = False
    for i in range(M):
        a, b, c = edges[i]
        if not ok[a]:
            continue
        if not ok[b]:
            continue
        newD = d[a]+c
        if newD < d[b]:
            upd = True
            d[b] = newD
    step += 1
    if step > N:
        flag = False
        break
if flag:
    ans = -d[N-1]
    ans = max(ans, 0)
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

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

INF = 10**10
# Bellman-Fordをするときは、辺集合を持つ
edges = [] 
# 1から行けない辺やNに到達できない辺を削除するための探索をする用
to = [[] for _ in range(2505)]
rto = [[] for _ in range(2505)]
reachableFrom1 = [False for _ in range(2505)]
reachableToN = [False for _ in range(2505)]
ok = [False for _ in range(2505)]

def dfs(v):
    if reachableFrom1[v]:
        return
    reachableFrom1[v] = True
    for u in to[v]:
        dfs(u)

def rdfs(v):
    if reachableToN[v]:
        return
    reachableToN[v] = True
    for u in rto[v]:
        rdfs(u)

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    c -= P
    c = -c # 最短路にするため符号を逆転
    edges.append([a, b, c])
    to[a].append(b)
    rto[b].append(a)

# 考えるべき頂点だけ洗い出し
dfs(0)
rdfs(N-1)
for i in range(N):
    ok[i] = reachableFrom1[i] & reachableToN[i]

# Bellman-Ford
d = [INF for _ in range(N)]
d[0] = 0
upd = True
step = 0
flag = True
while upd:
    upd = False
    for i in range(M):
        a, b, c = edges[i]
        if not ok[a]:
            continue
        if not ok[b]:
            continue
        newD = d[a]+c
        if newD < d[b]:
            upd = True
            d[b] = newD
    step += 1
    if step > N:
        flag = False
        break
if flag:
    ans = -d[N-1]
    ans = max(ans, 0)
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import numpy as np
n = int(input())
S = np.array([ list(input()) for _ in range(n) ])
ans = 0
for i in range(n):
  for j in range(n):
    M = S[:, [(l+j)%n for l in range(n)]]
    L = M[[(k+i)%n for k in range(n)], :]
    if (L==L.T).all():
      ans += 1 
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
S = np.array([ list(input()) for _ in range(n) ])
ans = 0
for j in range(n):
  M = S[:, [(l+j)%n for l in range(n)]]
  if (M==M.T).all():
    ans += n
print(ans)