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

from numba import njit

@njit
def solve(N, X, M):
    ans = 0
    a = X
    a0 = X
    for i in range(N):
        ans += a
        a = (a ** 2) % M
        if a == 1:
            ans += (N - i - 1)
            break
        if a == a0:
            w = i + 1
            k = N // w
            m = N % w
            ans *= k
            for i in range(m):
                ans += a
                a = (a ** 2) % M
            break
    return ans

N, X, M = [int(x) for x in input().split()]
ans = solve(N, X, M)
print(ans)

### FIXED CODE ###

import numpy as np
i8 = np.int64


def solve(N, X, M):
    memo_val = np.zeros(M, i8)
    memo_i = np.zeros(M, i8)
    ret = 0
    a = X
    for i in range(1, N):
        ret += a
        if memo_i[a] > 0:
            u = (N - memo_i[a]) // (i - memo_i[a])
            v = (N - memo_i[a]) % (i - memo_i[a])
            ret = u * (ret - memo_val[a])
            nokori = v + memo_i[a]
            for j in range(M):
                if memo_i[j] == nokori:
                    ret += memo_val[j]
            return ret
        memo_i[a] = i
        memo_val[a] = ret
        a = a ** 2 % M
    ret += a
    return ret

def main():
    f = open(0)
    N, X, M = [int(x) for x in f.readline().split()]
    ans = solve(N, X, M)
    print(ans)

main()
### BUGGY CODE ###

INF = float('inf')

def warshall_floyd(G):
    # ワーシャルフロイド法で移動距離を求める
    # G[x][y]: xからyへ直接移動するときの距離。直接移動できない場合はINF
    # 
    cost = [g[:] for g in G]
    N = len(G)
    # cost[i][j]: 頂点v_iから頂点v_jへ到達するための辺コストの和
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def main():
    N, M, L = map(int, input().split())

    # G[x][y]: xからyへ直接移動するときのコスト。移動できない場合はINF
    G = [[INF] * (N+1) for n in range(N+1)]

    for i in range(M):
        a, b, c = map(int, input().split())
        G[a][b] = c
        G[b][a] = c

    Q = int(input())
    Queries = []
    for i in range(Q):
        s, t = map(int, input().split())
        Queries.append((s, t))

    # ワーシャルフロイド法で、全点間の距離を求める
    cost = warshall_floyd(G)

    # 全点間の距離のうち、移動距離がL以内でおさまる頂点同士は、給油せずにすむ
    # そこで、全点間の距離のうち、移動距離がL以内でおさまる頂点同士を距離1で結んだグラフを作成し、
    # そのグラフに対してワーシャルフロイド法で最短距離を計算することで、
    # refuel[x][y] =「xからyへ移動するときの給油回数+1」というグラフを作成できる
    no_refuel = [[1 if x <= L else INF for x in c] for c in cost]

    refuel_count = warshall_floyd(no_refuel)

    ans = []
    for s, t in Queries:
        d = refuel_count[s][t]
        ans.append(d-1 if d != INF else -1)
    
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

### FIXED CODE ###

INF = float('inf')

def warshall_floyd(G):
    # ワーシャルフロイド法で移動距離を求める
    # G[x][y]: xからyへ直接移動するときの距離。直接移動できない場合はINF
    # 
    cost = [g[:] for g in G]
    N = len(G)
    # cost[i][j]: 頂点v_iから頂点v_jへ到達するための辺コストの和
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def main():
    N, M, L = map(int, input().split())

    # G[x][y]: xからyへ直接移動するときのコスト。移動できない場合はINF
    G = [[INF] * (N+1) for n in range(N+1)]

    for i in range(M):
        a, b, c = map(int, input().split())
        G[a][b] = c
        G[b][a] = c

    Q = int(input())
    Queries = []
    for i in range(Q):
        s, t = map(int, input().split())
        Queries.append((s, t))

    # ワーシャルフロイド法で、全点間の距離を求める
    cost = warshall_floyd(G)

    # 全点間の距離のうち、移動距離がL以内でおさまる頂点同士は、給油せずにすむ
    # そこで、全点間の距離のうち、移動距離がL以内でおさまる頂点同士を距離1で結んだグラフを作成し、
    # そのグラフに対してワーシャルフロイド法で最短距離を計算することで、
    # refuel[x][y] =「xからyへ移動するときの給油回数+1」というグラフを作成できる
    no_refuel = [[1 if x <= L else INF for x in c] for c in cost]

    refuel_count = warshall_floyd(no_refuel)

    ans = []
    for s, t in Queries:
        d = refuel_count[s][t]
        ans.append(d-1 if d != INF else -1)
    
    print(*ans, sep='\n')

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

A,B,N = map(int,input().split())
result = 0
for i in range(N//B+1):
    x = min(N,(i+1) * B -1)
    a = (A*x)//B
    b = A*(x//B)
    result = max(result,a-b)
print(result)

### FIXED CODE ###

A,B,N = map(int,input().split())
result = 0
x = min(N,B -1)
a = (A*x)//B
b = A*(x//B)
result = max(result,a-b)
print(result)
### BUGGY CODE ###

import sys
from math import floor
from math import factorial
from operator import mul
from functools import reduce
from collections import defaultdict
def main():
    def factorization(n):
        arr = []
        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
                arr.append([i, cnt])
        if temp != 1:
            arr.append([temp, 1])
        if arr == []:
            arr.append([n, 1])
        return arr
    n = int(input())
    if n == 1:
        print(1)
        sys.exit()

    from math import sqrt
    from math import ceil
    maxa = n  # maxa＝「素数判定したい数字のうち最大の数字」
    maxa2 = n
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    ps = {e: defaultdict(int) for e in range(n + 1)}
    nums = [i for i in range(n + 1)]
    for pe in prime_list:
        flag = True
        while flag:
            flag = False
            for i1 in range(2,n + 1):
                if nums[i1] % pe == 0:
                    nums[i1] /= pe
                    ps[i1][pe] += 1
                    flag = True

    r = 1
    for i1 in range(2, n + 1):
        pse = ps[i1]
        if pse:
            psv = pse.values()
            psv2 = [i + 1 for i in psv]
            tmp = reduce(mul, psv2)
            r += tmp * i1
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
from math import sqrt, floor
def main():
    n = int(input())
    if n == 1:
        print(1)
        sys.exit()
    # nd:num of div
    nd = [2] * (n + 1)

    for i1 in range(2, floor(n / 2) + 1):
        for i2 in range(i1 * 2, n + 1, i1):
            nd[i2] += 1

    r = 1
    for j1 in range(2, n + 1):
        r += nd[j1] * j1
    print(r)

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

import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
b = np.abs(a)
b1 = sorted(a,reverse = True)
b_k = b1[k-1] 
a_new = [a[_] for _ in range(len(a)) if b[_] >= b_k]
a_new.sort()
D = [[a_new[i+j-k] for j in range(k)] for i in range(len(a_new))]
A = (functools.reduce(operator.mul,D[_]) for _ in range(len(D)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]

    #動的計画法問題
    dp = [0] * (N+1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    else:
        dp[1] = 0

    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] = dp[i-1] + dp[i-2]
        
        dp[i] %= (10**9+7)

    print(dp[N]) 




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

# coding: utf-8
N, Q = map(int, input().split())
S = input()
l = [0] * N
c = 0
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
        l[i + 1] = c
for _ in range(Q):
    a, b = map(int, input().split())
    c = d = 0
    while a != 0:
        if l[a - 1] != 0:
            c = l[a - 1]
            break
        a -= 1
    while b > a:
        if l[b - 1] != 0:
            d = l[b - 1]
            break
        b -= 1
    print(max(d - c, 0))

### FIXED CODE ###

# coding: utf-8
N, Q = map(int, input().split())
S = input()
c = 0
lst = [0] * N
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    lst[i + 1] = c
for _ in range(Q):
    a, b = map(int, input().split())
    print(lst[b - 1] - lst[a - 1])
### BUGGY CODE ###


L,R = map(int,input().split())

b = 2018
for i in range(L,R+1):
    for j in range(i+1,R+1):
        a = (i*j)%2019
        b = min(b,a)
        if b == 0:
            break
print(b)

### FIXED CODE ###

L,R=map(int,input().split())
if R-L>=2019:
    minimum=0
else:
    left,right=L%2019,R%2019
    minimum=2018**2
    for i in range(left,right+1):
        for j in range(i+1,right+1):
            minimum=min(minimum,i*j%2019)
print(minimum)
### BUGGY CODE ###

import numpy as np 

N,K = map(int,input().split())
s=input()

ll = []
for i in range(len(s)):
    pre = "1"
    cnt0 = 0
    for j in range(i,len(s)):
        if s[j] != pre and s[j]=="0":
            cnt0 +=1
        pre = s[j]
        if cnt0 > K:
            break
        ll.append(j-i+1)
print(max(ll))

### FIXED CODE ###

import numpy as np 

N,K = map(int,input().split())
s=input()

li = []
ls = []
pre = "X"
for i in range(len(s)):
    if pre!=s[i]:
        li.append(i)
        ls.append(s[i])
    pre=s[i]
# print(li)
# print(ls)

for _ in range(K*2+1):
    li.append(N)

maxv = 0
for i in range(len(ls)):
    if ls[i] == "0":
        maxv = max(maxv, li[i+K*2]-li[i])
    else:
        maxv = max(maxv, li[i+K*2+1]-li[i])

print(maxv)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def f(n, q):
    stx = []
    for i in range(n):
        s, t, x = map(int, input().split())
        stx.append([s - x, t - x, x])
    stx.sort(key=lambda x: x[2])
    ds = []
    for i in range(q):
        d = int(input())
        for s, t, x in stx:
            if s <= d < t:
                print(x)
                break
        else:
            print(-1)

n, q = map(int, input().split())
f(n, q)


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    heapq.heappush(q,(c,h,w))

def main():
    dh=DH-1
    dw=DW-1
    while q:
        c,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        check(h-1,w-1,c+1)
        check(h-1,w+1,c+1)
        check(h+1,w-1,c+1)
        check(h+1,w+1,c+1)
        for i in [-2,+2]:
            for j in range(-2,3):
                check(h+i,w+j,c+1)
                check(h+j,w+i,c+1)
    return -1
print(main())

### FIXED CODE ###

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()
### BUGGY CODE ###

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

def syakutori():
    ans = 0
    bits = [0]*21
    r = 0
    l = 0
    flag = True
    #尺取り法をする
    while((l < len(nums)) or (not flag)):
        if not flag:
            #print("a", l, r, bits)
            for i, b in enumerate(bin(nums[r])[2:][::-1]):
                bits[i] -= int(b)
            r += 1
            flag = max(bits) <= 1
            if flag:
                ans += (l - r)

        #rを伸ばす(ついでに数え上げる)
        else:
            #print("ans", l, r, bits)
            for i, b in enumerate(bin(nums[l])[2:][::-1]):
                bits[i] += int(b)
            flag = max(bits) <= 1
            l += 1
            if flag:
                ans += (l - r)


    #lを縮める
    #後処理
    """
    while(r < len(nums)):
        if max(bits) > 1:
            for i, b in enumerate(bin(nums[r])[2:][::-1]):
                bits[i] -= int(b)
            print("c", l, r, bits)
            r += 1
        else:
            print("d", l, r, bits)
            r += 1
            ans += 1
    #次の判断のために加算、減産処理
    """
    return ans


print(syakutori())


### FIXED CODE ###

import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n = getN()
    lis = getList()
    xo, su = 0, 0
    ans = 0
    l, r = 0, 0
    forward = True
    while True:
        # print(l, r, ans, xo, su)
        if r == n:
            print(ans)
            return
        if forward:
            xo = xo^lis[r]
            su += lis[r]
            if xo == su:

                ans += r - l + 1
                r += 1
            else:
                forward = False
        else:
            xo = xo^lis[l]
            su -= lis[l]
            if xo == su:
                forward = True
                ans += r - l
                r += 1
                l += 1
            else:
                l += 1

def main():
    n = getN()
    for _ in range(n):
        solve()

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

def test():
  N, K = map(int, input().split())
  H = list(map(int, input().split()))
  dp = [float('inf')]*N
  dp[0] = 0

  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) 
    for j in range(max(i-K, 0), i))

  print(dp[-1])
 
if __name__ == '__main__':
  test()

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

def abs(x):
    if x >= 0:
        return x
    return -x

c = [0]
c.append(abs(h[1] - h[0]))
for i in range(2, n):
    cmin = None
    for cur in range(i-1, i-1-k, -1):
        if cur < 0:
            break
        val = abs(h[i] - h[cur]) + c[cur]
        if cmin is None or val < cmin:
            cmin = val
    c.append(cmin)

print(c[-1])
### BUGGY CODE ###

import math
import sys

def prime_calc(n):
    if n < 2:
        return False
    elif n==2 or n==3 or n==5 or n==7:
        return True
    else:
        rootN = math.floor(math.sqrt(n))
        i = 11
        while rootN > i:
            if n % i == 0:
                return False
            else:
                i += 2

    return True

def prime(n):
    cnt = 0
    for i in range(2, n+1):
        ans = prime_calc(i)
        if ans is True:
            cnt = cnt + 1

    return cnt

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

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

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += bisect.bisect_left(l[j+1:], l[i] + l[j])
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

import sys

N = int(input())
A = list(map(int,input().split()))
for i in range(N-1) :
    for j in range(i+1,N) :
        if A[i] == A[j] :
            print("NO")
            sys.exit()
print("YES")

### FIXED CODE ###

import sys

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
for i in range(N-1) :
    if A[i] == A[i+1] :
        print("NO")
        sys.exit()
print("YES")
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split(' ')))
mod = 10 ** 9 + 7
c = np.array([0, 0, 0])
ans = 1
for i in A:
    ans *= sum(c == i)
    if i == c[0]:
        c[0] += 1
    elif i == c[1]:
        c[1] += 1
    else:
        c[2] += 1
    ans %= mod
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
mod = 10 ** 9 + 7
c = [0, 0, 0]
ans = 1
for i in A:
    ans *= c.count(i)
    if i == c[0]:
        c[0] += 1
    elif i == c[1]:
        c[1] += 1
    else:
        c[2] += 1
    ans %= mod
print(ans)
### BUGGY CODE ###

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

pair = n*(n - 1)/2
not_4 = 0
ans = 'Yes'
for i in range(len(a)):
  for j in range(len(a)):
    
    if i == j or a[i]*a[j]%4 == 0:
      continue
    else:  
      not_4 += 1
      
      if not_4 >= pair:
        ans = 'No'
        break
    
print(ans)

### FIXED CODE ###

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

four = 0
two = 0
one = 0
for i in a:
  if i%4 == 0:
    four += 1
  elif i%2 == 0 and i%4 != 0:
    two += 1
  elif i%2 != 0:
    one += 1

if four >= one or four + 1 >= two//2 + two%2 + one or n == two:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

s=input()
q=int(input())
co=0
for i in range(q):
	a=input()
	if a[0]=="1":
#		s=s[::-1]
		co+=1
	elif a[2]=="1":
		if co%2 == 1:
			s=s[::-1]
			co=0
		s=a[4]+s
	else:
		if co%2==1:
			s=s[::-1]
			co=0
		s=s+a[4]
if co%2==1:
	s=s[::-1]
print(s)

### FIXED CODE ###

from collections import deque

deq=deque()
k = input()
for i in range(len(k)):
	deq.append(k[i])
q=int(input())
x=True
for i in range(q):
	a=input()
	if a[0]=="1":
		x = not x
	elif a[2]=="1":
		if x==True:
			deq.appendleft(a[4])
		else:
			deq.append(a[4])
	else:
		if x==True:
			deq.append(a[4])
		else:
			deq.appendleft(a[4])
if x==True:
	c="".join(deq)
else:
	deq.reverse()
	c="".join(deq)
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))

#ベルマンフォード N-1回
for _ in range(N):
	for a,b,c in fedge:
		D[b]=max( D[b],D[a]+c )

D1=copy.deepcopy(D)

#ベルマンフォード 追加1回で差分が出たら閉路検出
for a,b,c in fedge:
	if D[b]!=max( D[b],D[a]+c ):
		print -1
		quit()
else:
	print max(D[N],0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])