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

import numpy as np
N=int(input())
A=list(map(int,input().split()))
# cnt=[0]*(10**6+1)
cnt=np.zeros(10**6+1, dtype='int')
for a in A:cnt[a]+=1
 
if np.gcd.reduce(A)!=1:
  print("not coprime")
elif np.all([sum(cnt[i::i])<=1 for i in range(2,10**6+1)]):
  print("pairwise coprime")
else:
  print("setwise coprime")

### FIXED CODE ###

from math import gcd, sqrt, ceil
from functools import reduce

def sieve(n):
    A = list(range(n+1))
    for i in range(2, n+1 ,2):
        A[i] = 2
    for j in range(3, ceil(sqrt(n+1))+1, 2)[::-1]:
        for i in range(j, n+1, j):
            A[i] = j
    return A

def factorize(n, A):
    factors = set()
    while n != 1:
        f = A[n]
        factors.add(f)
        n //= f
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True
    A = sieve(10**6)
    all_factors = [0] * (10**6+1)
    for a in aa:
        factors = factorize(a, A)
        for factor in factors:
            if all_factors[factor]:
                pair_co = False
                break
            else:
                all_factors[factor] = 1
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))
### BUGGY CODE ###

from itertools import product
from sys import exit

def maxindexes(L,Lmax):
    ret = []
    for i in range(len(L)):
        if L[i] == Lmax:
            ret.append(i)
    
    return ret


H,W,M = map(int,input().split())
row = [0]*H
col = [0]*W
bomb = []

for _ in range(M):
    a,b = (int(x)-1 for x in input().split())
    row[a] += 1
    col[b] += 1
    bomb.append((a,b))

rmax = max(row)
cmax = max(col)

rmaxind= maxindexes(row,rmax)
cmaxind = maxindexes(col,cmax)

for p in product(rmaxind,cmaxind):
    if p not in bomb:
        print(rmax+cmax)
        exit(0)

print(rmax+cmax-1)

### FIXED CODE ###

from itertools import product
from sys import exit

def maxindexes(L,Lmax):
    ret = []
    for i in range(len(L)):
        if L[i] == Lmax:
            ret.append(i)
    
    return ret


H,W,M = map(int,input().split())
row = [0]*H
col = [0]*W
bomb = set([])

for _ in range(M):
    a,b = (int(x)-1 for x in input().split())
    row[a] += 1
    col[b] += 1
    bomb.add((a,b))

rmax = max(row)
cmax = max(col)

rmaxind= maxindexes(row,rmax)
cmaxind = maxindexes(col,cmax)
prod = product(rmaxind,cmaxind)

for p in prod:
    if p not in bomb:
        print(rmax+cmax)
        exit(0)

print(rmax+cmax-1)
### BUGGY CODE ###

k,s = map(int,input().split())
total = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if s == i+j+l:
                total+= 1
print(total)


### FIXED CODE ###

K,S = map(int,input().split())
cnt = 0
for i in range(K + 1):
    for j in range(K + 1):
        if i + j > S:
            continue
        elif i + j >= S - K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

s = input()
n = len(s)
count = 0

while True:
    if '111000' in s:
        count += s.count('111000') * 6
        s = s.replace('111000','')
    if '000111' in s:
        count += s.count('000111') * 6
        s = s.replace('000111','')
    if '1100' in s:
        count += s.count('1100') * 4
        s = s.replace('1100','')
    if '0011' in s:
        count += s.count('0011') * 4
        s = s.replace('0011','')
    if '10' in s:
        count += s.count('10') * 2
        s = s.replace('10','')
    elif '01' in s:
        count += s.count('01') * 2
        s = s.replace('01','')
    else:
        break

print(count)


### FIXED CODE ###

s = input()
print(min(s.count('0'),s.count('1'))*2)
### BUGGY CODE ###

n,m,s,t = map(int,input().split())
infinit = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuuk = [[] for _ in range(n)]

for _ in range(m):
        u,v,a,b = map(int,input().split())
        gyen[u-1].append([v-1,a])
        gyen[v-1].append([u-1,a])
        gsnuuk[u-1].append([v-1,b])
        gsnuuk[v-1].append([u-1,b])

def dijkstra(graf, start):
        distance = [infinit for _ in range(n)]
        distance[start] = 0
        pre = start
        q = []
        q.extend(range(n))
        q.remove(start)
        while q:
                for i in graf[pre]:
                        distance[i[0]] = min(distance[pre]+i[1],distance[i[0]])
                tmp = infinit
                for i in q:
                        if distance[i] <= tmp:
                                tmp = distance[i]
                                pre = i
                q.remove(pre)
        return distance

distance_from_start = dijkstra(gyen,s-1)
distance_from_goal = dijkstra(gsnuuk,t-1)

for i in range(n):
        ans = infinit
        for j in range(i,n):
                tmp = distance_from_start[j] + distance_from_goal[j]
                if tmp < ans:
                        ans = tmp
        print(infinit - ans)

### FIXED CODE ###

import heapq
import sys
from itertools import accumulate

n,m,s,t = map(int,next(sys.stdin).split(" "))
inf = 1000000000000000
gyen = [dict() for _ in range(n)]
gsnuk = [dict() for _ in range(n)]

for _ in range(m):
        u,v,a,b = map(int,next(sys.stdin).split(" "))
        gyen[u-1][v-1] = gyen[v-1][u-1] = a
        gsnuk[u-1][v-1] = gsnuk[v-1][u-1] = b

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                du, u = heapq.heappop(q)
                if dist[u] < du:
                        continue
                for v,d in graph[u].items():
                        if dist[v] > du+d:
                                dist[v] = du+d
                                heapq.heappush(q, (dist[v], v))
        return dist

yen = dijkstra(gyen,s-1)
snuke = dijkstra(gsnuk,t-1)

ans = list(accumulate([y+s for y,s in zip(yen,snuke)][::-1],min))
[print(inf-ans[i]) for i in range(n-1,-1,-1)]
### BUGGY CODE ###

from collections import deque

def bfs(H,W,S):
    qu = deque([(0,0,1)])
    while(len(qu) != 0):
        p,q,r = qu.popleft()
        S[p][q] = '#'
        for d in [(-1,0), (0,-1), (1,0), (0,1)]:
            s = p+d[0]
            t = q+d[1]
            if (s < 0 or t < 0 or s >= H or t >= W):
                continue
            if (s == (H-1) and t == (W-1) and S[s][t] == '.'):
                return r+1
            if S[s][t] == '.':
                qu.append((s,t,r+1))
    return -1

H, W = list(map(int, input().split()))
S = []

cnt = 0
for i in range(H):
    a = input()
    tmp = []
    for i in a:
        if (i == '.'):
            cnt += 1
        tmp.append(i)
    S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
    print(cnt - step)
else:
    print(step)


### FIXED CODE ###

from collections import deque

def bfs(H,W,S):
	V = [[False for i in range(W)] for j in range(H)]
	qu = deque([(0,0,1)])
	V[0][0] = True
	while(qu):
		p,q,r = qu.popleft()
		S[p][q] = '#'
		for d in [(-1,0), (0,-1), (1,0), (0,1)]:
			s = p+d[0]
			t = q+d[1]
			if s < 0 or t < 0 or s >= H or t >= W:
				continue
			if s == (H-1) and t == (W-1) and S[s][t] == '.':
				return r+1
			if S[s][t] == '.' and V[s][t] == False:
				V[s][t] = True
				qu.append((s,t,r+1))
	return -1

H, W = list(map(int, input().split()))
S = []
cnt = 0
for i in range(H):
	a = str(input())
	tmp = []
	for i in a:
		if (i == '.'):
			cnt += 1
		tmp.append(i)
	S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
	print(cnt - step)
else:
	print(step)
### BUGGY CODE ###

n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)

### FIXED CODE ###

n=int(input())
t=list(map(int,input().split()))
T=[-1,0]
for i in range(n):
  T.append(T[-1]+t[i])
T.append(T[-1]+1)
V=[0]+list(map(int,input().split()))+[0]
VV=[110]*(2*T[-1]+1)
for i in range(n+2):
  for j in range(2*T[-1]+1):
    if j<2*T[i]:
      a=T[i]-j/2
      VV[j]=min(VV[j],a+V[i])
    elif 2*T[i]<=j and j<=2*T[i+1]:
      VV[j]=min(VV[j],V[i])
    else:
      a=j/2-T[i+1]
      VV[j]=min(VV[j],a+V[i])
print(sum(VV)/2)
### BUGGY CODE ###

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

ans=0
RGB=[]
for i in range(N-2):
  RGB.append(S[i])
  for j in range(i+1,N-1):
    if S[i]!=S[j]:
      RGB.append(S[j])
      if not 'R' in RGB:
        ans+=S[j+1:].count('R')
        if 2*j-i<N and S[2*j-i]=='R':
          ans-=1
      elif not 'G' in RGB:
        ans+=S[j+1:].count('G')
        if 2*j-i<N and S[2*j-i]=='G':
          ans-=1
      else:
        ans+=S[j+1:].count('B')
        if 2*j-i<N and S[2*j-i]=='B':
          ans-=1
    RGB=[S[i]]
  RGB=[]
print(ans)

### FIXED CODE ###

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

r=S.count('R')
g=S.count('G')
b=S.count('B')

ans=r*g*b
for i in range(N-2):
  for j in range(i+1,N-1):
    if 2*j-i>=N:
      break
    elif S[i]!=S[j] and S[j]!=S[2*j-i] and S[2*j-i]!=S[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

def get_primes(n):
    assert n >= 2
    is_prime = [False if i % 2 == 0 else True for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = True
    for i in range(3, n + 1, 2):
        if i ** 2 >= n:
            break
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    return [i for i, b in enumerate(is_prime) if b == True]


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    primes = get_primes(max(max(A), 3))
    prime_indices = {p: i for i, p in enumerate(primes)}
    lcm_pf = [0 for _ in range(len(primes))]
    a_pf = [[0 for _ in range(len(primes))] for _ in range(N)]
    # lcm(A) の素因数分解表示を計算
    for i, a in enumerate(A):
        for j, p in enumerate(primes):
            while a % p == 0:
                a_pf[i][j] += 1
                a //= p
            if a == 1:
                break
            if p ** 2 > a:
                # 'a' is a prime
                a_pf[i][prime_indices[a]] += 1
                break
        for j in range(len(primes)):
            lcm_pf[j] = max(lcm_pf[j], a_pf[i][j])
    # sum(lcm(A) / A) を計算
    ans = 0
    for i in range(N):
        v = 1
        for j, p in enumerate(primes):
            e = lcm_pf[j] - a_pf[i][j]
            v *= p ** e
            v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    L = 1
    for a in A:
        L = L * a // math.gcd(L, a)
    ans = 0
    for a in A:
        ans += L * pow(a, MOD - 2, MOD)
        ans %= MOD
    print(ans)


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

n=int(input())
a=[int(input()) for i in range(n)]
tmp=[]
i=1
while i>0:
  i=a[i-1]
  if i in tmp:
    print(-1)
    break
  tmp+=[i]
  if i==2:
    print(len(tmp))
    break

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
tmp=[]
i=1
cnt=0
while cnt<=n:
  i=a[i-1]
  cnt+=1
  if i==2:
    print(cnt)
    break
else:
  print(-1)
### BUGGY CODE ###

N=int(input())
X=[]
for i in range(1,10):
    x=[]
    for j in range(1,10):
        c=0
        for k in range(1,N+1):
            if((str(k)[0]==str(i))&(str(k)[-1]==str(j))):
                c+=1
        x.append(c)
    X.append(x)
Ans=0
for i in range(9):
    for j in range(9):
        Ans+=X[i][j]*X[j][i]
    
print(Ans)

### FIXED CODE ###

n=int(input())
ans=0
X=[[0]*10 for i in range(10)]
for i in range(1,n+1):
    t=(int)(str(i)[0])
    b=(int)(str(i)[-1])
    X[t][b]+=1

for i in range(1,10):
    for j in range(1,10):
        ans+=X[i][j]*X[j][i]

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

S = input()
Q = int(input())
q = []
for i in range(Q):
    a = input().split(" ")
    if len(a) == 1:
        q.append([int(a[0])])
    else:
        q.append([int(a[0]), int(a[1]), a[2]])

#print(S)
#print(q)


direction = 1 #通常の向き　-1:反対方向

for t in range(len(q)):
    T = q[t]
    if T[0] == 1:
        direction *= -1
    else:
        F = T[1]
        C = T[2]
        if F == 1:
            if direction == 1:
                S = C + S
            else:
                S = S + C
        else:
            if direction == 1:
                S = S + C
            else:
                S = C + S

if direction == 1:
    print(S)
else:
    SS = ""
    for i in range(len(S)):
        SS += S[len(S) - i - 1]
    print(SS)

### FIXED CODE ###

S = input()
Q = int(input())
q = []
for i in range(Q):
    a = input().split(" ")
    if len(a) == 1:
        q.append([int(a[0])])
    else:
        q.append([int(a[0]), int(a[1]), a[2]])

#print(S)
#print(q)

def switch(s):
    d = ""
    for i in range(len(s)):
        d += s[len(s) - i - 1]
    return d

H = ""
B = ""

direction = 1 #通常の向き　-1:反対方向

for t in range(len(q)):
    T = q[t]
    if T[0] == 1:
        direction *= -1
    else:
        F = T[1]
        C = T[2]
        if F == 1:
            if direction == 1:
                H += C
            else:
                B += C
        else:
            if direction == 1:
                B += C
            else:
                H += C

if direction == 1:
    print(switch(H) + S + B)
else:
    print(switch(B) + switch(S) + H)
### BUGGY CODE ###

n,w = map(int,input().split())
value = []
weight = []
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    x,y = map(int,input().split())
    value += [y]
    weight += [x]
for i in range(n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j-weight[i]]+value[i])
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[n][w])

### FIXED CODE ###

nums, weight = map(int,input().split())
ary  = [0 for i in range(nums)]
for i in range(nums):
    ary[i] = list(map(int,input().split()))
dp =[[0 for i in range(weight+1)]for i in range(nums+1)]
 
check = 0
for i in range(nums):
    for x in range(weight+1):
        if x - ary[i][0] >= 0:
            check = dp[i][x -ary[i][0]] + ary[i][1]
            if check > dp[i+1][x]:
                dp[i+1][x] = check
 
        check = dp[i][x]
        if check > dp[i+1][x]:
            dp[i+1][x] = check
 
print(dp[nums][weight])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


@lru_cache(maxsize=None)
def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(numbers, queries, D):
    for l, r in queries:
        ans = 0
        while True:
            if l == r:
                break
            res = sub_solve(l, l+D)
            ans += res
            l += D
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())
    board = []
    for _ in range(H):
        board.append([int(x) for x in input().split()])
    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    for y, row in enumerate(board, start=1):
        for x, i in enumerate(row, start=1):
            numbers[i] = [x, y]

    solve(numbers, queries, D)


if __name__ == '__main__':
    main(sys.argv[1:])
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(queries, H, W, D):
    dp = [0] * (H*W+1)
    for i in range(D+1, H*W+1):
        dp[i] = dp[i-D] + sub_solve(i-D, i)

    for l, r in queries:
        ans = dp[r] - dp[l]
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())

    for y in range(1, H+1):
        tmp = [int(x) for x in input().split()]
        for x, i in enumerate(tmp, start=1):
            numbers[i] = (x, y)

    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    solve(queries, H, W, D)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

def rep(b,r,N):
    return (N-r)//b+1 if r>0 else N//b

N,K=map(int,input().split(' '))
count = 0
for b in range(K+1,N+1):
    for r in range(K,b):
        count += rep(b,r,N)
print(count)

### FIXED CODE ###


N,K=map(int,input().split(' '))
count = 0
for b in range(K+1,N+1):
    l, h, n = K, b-1, b-K
    while l <= N:
        if h <= N:
            count += n
            if l==0:
                count -=1
        else:
            count += N-l+1
            if l==0:
                count -=1
            break
        l+=b
        h+=b
print(count)
### BUGGY CODE ###

N = int(input())

p = 1

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

print(p % (10**9 + 7))

### FIXED CODE ###

N = int(input())

p = 1

for i in range(N):
    i += 1
    p *= i
    p %= 10**9 + 7

print(p)
### BUGGY CODE ###

from sys import maxsize


def solve(ls, n, k):
	dp = [maxsize] * n
	dp[0] = 0
	if n == 1:
		return 0
	dp[1] = abs(ls[1] - ls[0])
	for i in range(2, n):
		j = 1
		while j <= k and i - j >= 0:
			dp[i] = (min((dp[i - j] + abs((ls[i - j]) - ls[i])),dp[i]))
			j+=1

	return dp[n-1]


n, k = map(int, input().split())
ls = list(map(int, input().split()))
print(solve(ls, n, k))


### FIXED CODE ###

from sys import stdout, stdin, maxsize

n, k = map(int, stdin.readline().split())
ls = list(map(int, stdin.readline().split()))
dp = [maxsize] * (n + 1)
dp[1] = 0
if n == 1:
	print(0)
else:
	dp[2] = abs(ls[1] - ls[0])
	for i in range(3, n + 1):
		j = 1
		while j <= k and i - j >= 0:
			dp[i] = min(dp[i - j] + abs(ls[i - 1] - ls[i - 1 - j]), dp[i])
			j += 1
	print(dp[n])
### BUGGY CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
import numpy as np

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  A=np.cumsum(D)
  return A 

for i in range(min(K,42)):
  A=list(f(A))  
  
print(*A[:-1])


### FIXED CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for i in range(1,N):
    D[i]+=D[i-1]
  A=D[:-1]
  return A 

for i in range(min(K,42)):
  A=f(A)
print(*A)
### BUGGY CODE ###

M = int(input())
DC = [list(map(int,input().split())) for _ in [0]*M]

ans = 0
res = []
for d,c in DC:
    while c>0:
        if c%2==1:
            res.append(d)
            c -=1
        d *= 2
        if d>=10:
            d = d//10 + d%10
            ans += c
            c//=2
        else:
            ans += c//2
            c//=2

tmp = 0
for r in res:
    ans += 1
    tmp += r
    if tmp >= 10:
        tmp -=9
        ans += 1
ans -=1
print(ans)

### FIXED CODE ###

M = int(input())
DC = [list(map(int,input().split())) for _ in [0]*M]

ans = 0
res = []
for d,c in DC:
    while c>0:
        if c%2==1:
            res.append(d)
            c -=1
        d *= 2
        if d>=10:
            d = d//10 + d%10
            ans += c
            c//=2
        else:
            ans += c//2
            c//=2

tmp = 0
for r in res:
    ans += 1
    tmp += r
    if tmp >= 10:
        tmp -=9
        ans += 1
ans -=1
print(ans)
### BUGGY CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        c1 *= (n+1-i)*pow(i,M-2,M)%M
        c2 *= (n-i)*pow(i,M-2,M)%M
        y += c1*c2%M
print(y%M)


### FIXED CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        p = pow(i,M-2,M)
        c1 = c1*(n+1-i)*p%M
        c2 = c2*(n-i)*p%M
        y += c1*c2%M
        # y = (y+c1*c2)%M
print(y%M)
### BUGGY CODE ###

N, M, P = map(int,input().split())
dist = [0] + [float('inf')] * (N - 1)

a = []
b = []
c = []

for i in range(M):
    i,j,k = map(int,input().split())
    a.append(i)
    b.append(j)
    c.append(-1*(k - P))

INF = float('inf')

for i in range(N-1):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
        
ans = dist[N -1]

negative = [False] * N

for i in range(N):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
            negative[b[j] - 1] = True

        if negative[a[j] - 1] == True:
            negative[b[j] - 1] = True

if negative[N - 1]:
    print(-1)
else:
    print(max(-1 * ans, 0))


### FIXED CODE ###

N, M, P = map(int,input().split())
dist = [0] + [float('inf')] * (N - 1)

a = []
b = []
c = []

for i in range(M):
    i,j,k = map(int,input().split())
    a.append(i)
    b.append(j)
    c.append(-1*(k - P))

INF = float('inf')

for i in range(N-1):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
        
ans = dist[N -1]

negative = [False] * N

for i in range(N):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
            negative[b[j] - 1] = True

        if negative[a[j] - 1] == True:
            negative[b[j] - 1] = True

if negative[N - 1]:
    print(-1)
else:
    print(max(-1 * ans, 0))
### BUGGY CODE ###

import math

K = int(input());
gcd = 0;
gcd1 = 0;

for a in range(K):
  aa = a + 1 ;
  
  for b in range(K):
    bb = b + 1;
    
    for c in range(K):
      cc = c + 1;
      gcd1 = math.gcd(aa,bb);
      gcd += math.gcd(gcd1,cc);
      
print(gcd)

### FIXED CODE ###

from math import gcd
 
K = int(input());
sum = 0;

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      sum += gcd(gcd(a,b),c);

print(sum)
### BUGGY CODE ###

class Node:
    def __init__(self, index):
        self.count = 0
        self.fr = -1
        self.index = index


N, Q = map(int, input().split())
node = [Node(i) for i in range(N)]
for i in range(N - 1):
    fr, to = map(int, input().split())
    node[to - 1].fr = fr - 1

for i in range(Q):
    fr, c = map(int, input().split())
    node[fr- 1].count += c
    
for i in range(N):
    x = node[i].count
    next = node[i].fr
    while next != -1:
        x += node[next].count
        next = node[next].fr
    if not i == N:
        print(x, end=' ')
    else:
        print(x)





### FIXED CODE ###

class Node:
    def __init__(self, index):
        self.count = 0
        self.fr = -1
        self.index = index


N, Q = map(int, input().split())
node = [Node(i) for i in range(N)]
for i in range(N - 1):
    fr, to = map(int, input().split())
    node[to - 1].fr = fr - 1

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

print(node[0].count, end=' ')

for i in range(1, N):
    node[i].count += node[node[i].fr].count
    if not i == N:
        print(node[i].count, end=' ')
    else:
        print(node[i].count)