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

import sys
sys.setrecursionlimit(10 ** 5)


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]

graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
query = query[::-1]

dp = [[-1] * (10 + 1) for i in range(n)]
first = [0] * n
def solve(v, d, c):
    if d < 0:
        return
    if dp[v][d] != -1:
        return
      
    dp[v][d] = c
    if first[v] == 0:
        first[v] = c

    solve(v, d - 1, c)
    for u in graph[v]:
        solve(u, d - 1, c)
    return
  

for v, d, c in query:
    v -= 1
    solve(v, d, c)

for i in range(n):
    print(first[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]


graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
query = query[::-1]

dp = [-1] * (n * (10 + 1))
# dp = [[-1] * (10 + 1) for i in range(n)]
# [v][d] -> [v * 11 + d]
first = [0] * n

def solve(v, d, c):
    if d < 0 or dp[v * 11 + d] != -1:
        return
      
    dp[v * 11 + d] = c
    if first[v] == 0:
        first[v] = c

    solve(v, d - 1, c)
    for u in graph[v]:
        solve(u, d - 1, c)
    return
  

for v, d, c in query:
    v -= 1
    solve(v, d, c)

for i in range(n):
    print(first[i])
### BUGGY CODE ###

from bisect import bisect_left as bl
from collections import deque
A, B, Q = map(int, input().split())
inf = 10 ** 11
Sh = [int(input()) for _ in range(A)] + [inf, inf]
Te = [int(input()) for _ in range(B)] + [inf, inf]

for _ in range(Q):
  q = int(input())
  temp = inf
  i = bl(Sh, q)
  #print(q, Sh[i - 1])
  que = deque([])
  que.append(i)
  if i != 0:
    que.append(i - 1)
  while len(que):
    j = que.popleft()
    k = bl(Te, Sh[j])
    #print(Sh[j], Te[k])
    temp = min(temp, abs(Sh[j] - Te[k]) + abs(Sh[j] - q))
    if k != 0:
      temp = min(temp, abs(Sh[j] - Te[k - 1]) + abs(Sh[j] - q))
    
  i = bl(Te, q)
  que.append(i)
  if i != 0:
    que.append(i - 1)
  while len(que):
    j = que.popleft()
    k = bl(Sh, Te[j])
    temp = min(temp, abs(Te[j] - Sh[k]) + abs(Te[j] - q))
    if k != 0:
      temp = min(temp, abs(Te[j] - Sh[k - 1]) + abs(Te[j] - q))
  print(temp)
    

### FIXED CODE ###

from bisect import bisect_left as bl
A, B, Q = map(int, input().split())
inf = 10 ** 11
Sh = [-1 * inf] + [int(input()) for _ in range(A)] + [inf]
Te = [-1 * inf] + [int(input()) for _ in range(B)] + [inf]
for _ in range(Q):
  x = int(input())
  b, d = bl(Sh, x), bl(Te, x)
  res = inf
  for S in [Sh[b - 1], Sh[b]]:
    for T in [Te[d - 1], Te[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
### BUGGY CODE ###

#ABC073-C
n = int(input())
paper = []
for _ in range(n):
    a = int(input())
    if a in set(paper):
        paper.remove(a)
    else:
        paper.append(a)

print(len(paper))
    

### FIXED CODE ###

#ABC073-C
from collections import Counter
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
  
cnt = 0
c = Counter(a)
for i in c.values():
    if i % 2 == 0:
        continue
    else:
        cnt += 1
        
print(cnt)
### BUGGY CODE ###

import copy
import numpy as np
from math import factorial

def num_choice_2(N):
    if N > 1:
        return N * (N - 1) // 2
    else:
        return 0

N = int(input())
A = [int(x) for x in input().split()]

nums = np.zeros(N, dtype=int)
for a_i in A:
    nums[a_i - 1] += 1

for i in range(N):
    nums[A[i] - 1] -= 1
    ans = np.sum([num_choice_2(x) for x in nums])
    nums[A[i] - 1] += 1
    print(ans)

### FIXED CODE ###

def n_c_2(n):
    if n < 1:
        return 0
    else:
        return n * (n - 1) // 2

N = int(input())
A = [int(x) for x in input().split()]

n_balls = [0 for _ in A]
for a_i in A:
    n_balls[a_i - 1] += 1

n_combinations = [n_c_2(n) for n in n_balls]
total_combinations = sum(n_combinations)

for i, a_i in enumerate(A):
    diff = n_c_2(n_balls[a_i - 1]) - n_c_2(n_balls[a_i - 1] - 1)
    print(total_combinations - diff)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]

memo = [[[0] * 4 for _ in range(W)] for _ in range(H)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, i):
	nx = x + dx[i]
	ny = y + dy[i]
	if nx >= 0 and nx < H and ny >= 0 and ny < W and memo[nx][ny][i] > 0:
		memo[x][y][i] = memo[nx][ny][i] + 1
		return memo[x][y][i]
	elif nx >= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] == '.':
		memo[x][y][i] = dfs(nx, ny, i) + 1
		return memo[x][y][i]
	else:
		return 0
		
ans = 0

for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == '.':
			tmp = 1
			for j in range(4):
				tmp += dfs(sx, sy, j)
				
			if tmp > ans:
				ans = tmp
				
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]
R = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == '.':
			if j > 0:
				L[i][j] = L[i][j - 1] + 1
			elif j == 0:
				L[i][j] = 1
				
			if i > 0:
				U[i][j] = U[i - 1][j] + 1
			elif i == 0:
				U[i][j] = 1
		
		if S[i][W - j - 1] == '.':
			if j > 0:
				R[i][W - j - 1] = R[i][W - j] + 1
			elif j == 0:
				R[i][W - j - 1] = 1
		
		if S[H - i - 1][j] == '.':
			if i > 0:
				D[H - i - 1][j] = D[H - i][j] + 1
			elif i == 0:
				D[H - i - 1][j] = 1
			
ans = 0
for i in range(H):
	for j in range(W):
		tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
		if tmp > ans:
			ans = tmp
			
print(ans)
### BUGGY CODE ###

n = int(input())
numbers = list(map(int,input().split()))
cnt = 0
for i in range(n):
    if min(numbers[:i+1]) >= numbers[i]:
        cnt += 1

print(cnt)
    

### FIXED CODE ###

n = int(input())
numbers = list(map(int,input().split()))
cnt = 0
a = 2*10**5
for i in range(n):
    a = min(numbers[i],a)
    if a >= numbers[i]:
        cnt += 1

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

n = int(input())

list = [sorted(list(input())) for i in range(n)]

counter = 0

for i in range(n):
  for j in range(n):
    if list[i]==list[j]:
      counter += 1
      
answer = int((counter-n)/2)

print(answer)

### FIXED CODE ###

from collections import Counter

N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]

c = Counter(s)

ans = 0

for key in c:
  n = c[key]
  ans += n * (n-1)/2

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

input()
L = list(map(int, input().split()))
M = [i-1 for i in L]
P = [i+1 for i in L]
a = list(set(L)|set(M)|set(P))
answer = 0
for i in a:
    x = L.count(i)+L.count(i-1)+L.count(i+1)
    if answer<x:
        answer = x
print(answer)

### FIXED CODE ###

input()
L = list(map(int, input().split()))
m = min(L)
M = max(L)
a = [0]*(M-m+3)
for i in L:
    a[i-m] += 1
    a[i-m+1] += 1
    a[i-m+2] += 1
print(max(a))
### BUGGY CODE ###

A,B=map(int,input().split())
mod = 2018

for i in range(A,B):
  x = i % 2019
  for j in range(i+1,B+1):
    j = j % 2019
    mod = min(mod, (x*j)%2019)

print(mod)

### FIXED CODE ###

A,B=map(int,input().split())
mod = 2018
flag =0
for i in range(A,B):
  x = i % 2019
  for j in range(i+1,B+1):
    j = j % 2019
    mod = min(mod, (x*j)%2019)
    if mod == 0:
      flag = 1
      break
  if flag:
    break

print(mod)
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))
cnt=0
for i in range(1,n+1):
	if l[i-1]==min(l[:i]):
		cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
cnt=1
nmin=l[0]
for i in range(1,n):
	if nmin>=l[i]:
		cnt+=1
		nmin=l[i]
print(cnt)
### BUGGY CODE ###

class Bit:
    """1-indexed"""

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, Q = map(int, input().split())
C = tuple(map(int, input().split()))
queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append((l, r, i))
queries.sort(key=lambda x: x[1])

b = Bit(N)
last = [None] * (N + 1)

cur = 1
ans = [None] * Q
for l, r, i in queries:
    while cur <= r:
        if last[C[cur - 1]] is not None:
            b.add(last[C[cur - 1]], -1)
        last[C[cur - 1]] = cur
        b.add(cur, 1)
        cur += 1
    ans[i] = b.sum(r) - b.sum(l - 1)
print(*ans, sep='\n')


### FIXED CODE ###

import sys

input = sys.stdin.readline


class Bit:
    """1-indexed"""

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, Q = map(int, input().split())
C = tuple(map(int, input().split()))
queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append((l, r, i))
queries.sort(key=lambda x: x[1])

b = Bit(N)
last = [None] * (N + 1)

cur = 1
ans = [0] * Q
for l, r, i in queries:
    while cur <= r:
        if last[C[cur - 1]] is not None:
            b.add(last[C[cur - 1]], -1)
        last[C[cur - 1]] = cur
        b.add(cur, 1)
        cur += 1
    ans[i] = b.sum(r) - b.sum(l - 1)
print(*ans, sep='\n')
### BUGGY CODE ###

########### E
H, W, M = map(int, input().split())
bombs = []
for _ in range(M):
    bomb = list(map(int, input().split()))
    bombs.append(bomb)
 
H_list = [0]*H
W_list = [0]*W
sign = True
for i in range(M):
    H_list[bombs[i][0]-1] += 1
    W_list[bombs[i][1]-1] += 1
 
max_H = [i for i,k in enumerate(H_list) if k == max(H_list)]
max_W = [i for i,k in enumerate(W_list) if k == max(W_list)]
 
cross = []
 
for i in max_H:
    for k in max_W:
        if [i+1,k+1] not in bombs:
            sign = False
            print(max(H_list) + max(W_list))
            break
    break
 
if sign:
    print(max(H_list) + max(W_list) -1)

### FIXED CODE ###

import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
            # 即座に探索を終了する. これによりループの回数は最大でもM+1回となる.
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+sum(A[l:r])
            return dp[l][r-1]


dfs(0, N)
# print(dp)
#print("ans->", dp[0][-1])
print(dp[0][-1])


### FIXED CODE ###

from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float(0)]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


# print(a_acc)
bfs()
# print(dp)
ans = int(dp[0][-1])
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,(input().split(' '))))
#b = sorted(a)
ans = []
#l = range(0,n)
x = [print(a.index(i)+1) for i in range(1,n+1)]
   
#print(x)  
#print(' '.join(x))

### FIXED CODE ###

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

from collections import OrderedDict
od = OrderedDict()

for n,i in enumerate(a):
  od[(n+1)] = i

#print(od)

od_sorted_value = OrderedDict(
    sorted(od.items(), key=lambda x: x[1], reverse=False)
)
#print(od_sorted_value)

ans = list(od_sorted_value.items())
for i,n in ans:
  print(i)
### BUGGY CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
uf = UnionFind(N)
query = [list(map(int, input().split())) for _ in range(M)]
ans = C(N,2)
ans_arr = [0]*M
ans_arr[M-1] = ans
for i in range(M-1):
    A, B = query[M-1-i][0]-1, query[M-1-i][1]-1
    if not uf.same(A,B):
        a_members = len(uf.members(A))
        b_members = len(uf.members(B))
        uf.union(A,B)
        ans -= a_members * b_members
    ans_arr[M-2-i] = ans
for i in ans_arr:
    print(i)

### FIXED CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
uf = UnionFind(N)
query = [list(map(int, input().split())) for _ in range(M)]
ans = C(N,2)
ans_arr = [0]*M
ans_arr[M-1] = ans
for i in range(M-1):
    A, B = query[M-1-i][0]-1, query[M-1-i][1]-1
    if not uf.same(A,B):
        ans -= uf.size(A) * uf.size(B)
    ans_arr[M-2-i] = ans
    uf.union(A,B)
for i in ans_arr:
    print(i)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  STX = sorted(STX,key=lambda x:x[2])
  for s,t,x in STX:
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort(reverse=True)
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 1
	for i in range(N):
		if (sum(a)-sum_list[i])*2 >= a[i]:
			count += 1
		else:
			break

	print(count)

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort()
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 0
	for i in range(N-1):
		if 2*sum_list[i] < a[i+1]:
			count = i+1

	print(N-count)

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

n=int(input())

ans=0
for i in range(n):
  ans+=i
print(ans)

### FIXED CODE ###

n=int(input())

ans=0
for i in range(n):
  ans+=i
print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())

dpt = [math.inf] * N
steps = list(map(int, input().split()))
dpt[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i + j > N - 1:
            break
        ij = i + j
        x = dpt[i] + abs(steps[i] - steps[ij])
        if x < dpt[ij]:
            dpt[ij] = x

print(dpt[N-1])


### FIXED CODE ###

import math
step_n, max_jump = map(int, input().split())

step_list = list(map(int, input().split()))

dp_table = [math.inf] * (step_n)
dp_table[0] = 0

for i in range(1, step_n):
    min_from = max(0, i - max_jump)
    dp_table[i] = min(dp_table[j] + abs(step_list[i] - step_list[j]) for j in range(min_from, i))

print(dp_table[step_n-1])
### BUGGY CODE ###

INF=10**30
def Belman_Ford(s,N,Edge):
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg
                
N,M,P=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    Edge.append((a-1,b-1,-(c-P)))
dist,neg=Belman_Ford(0,N,Edge)

if(neg[N-1]):
    print(-1)
else:
    ans=-dist[N-1]
    print(max(0,ans))

### FIXED CODE ###

INF=10**30
def Belman_Ford(s,N,Edge):
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg
                
N,M,P=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    Edge.append((a-1,b-1,-(c-P)))
dist,neg=Belman_Ford(0,N,Edge)

if(neg[N-1]):
    print(-1)
else:
    ans=-dist[N-1]
    print(max(0,ans))
### BUGGY CODE ###

import collections
import math
 
def combinations_count(n, r):
    return 0 if n < r else math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
#print(combi)

for i in range(N):
  ans = 0
  
  # i番目の要素をcombiからdecrement
  combi[A[i]] -= 1
  
  #print(combi)
  
  for v in combi.values():
    #print(v)
    ans += combinations_count(v, 2)
  
  print(ans)

  # i番目の要素をcombiからincrement
  combi[A[i]] += 1

### FIXED CODE ###

import collections
import math
 
def combinations_count(n, r):
  if n == r:
    return 1
  elif n < r:
    return 0
  else:
    return n * (n-1) // 2 
    #math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
combi_count = {}
calc_dict = {}
total = 0
for k, v in combi.items():
  if v in calc_dict:
    combi_count[k] = calc_dict[v]
  else:
    combi_count[k] = combinations_count(v, 2)
    calc_dict[v] = combi_count[k]
  total += combi_count[k]

for i in range(N):
  ans = total - combi_count[A[i]] + combinations_count(combi[A[i]]-1, 2)
  print(ans)
### BUGGY CODE ###

n = int(input())
s = 1
for i in range(1, n + 1):
    s = s * i
print(s % (10 ** 9 + 7))


### FIXED CODE ###

n = int(input())
s = 1
m = 10 ** 9 + 7
for i in range(1, n + 1):
    s = (s * i) % m
print(s)
### BUGGY CODE ###

import fractions
import functools
import sys

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
count = 0
#lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
for i in range(N):
    count += functools.reduce(lcm_base, A, 1)//A[i]

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

### FIXED CODE ###

import fractions
import functools
import sys

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]
#B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))
### BUGGY CODE ###

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

for i in a:
  multi *= i

if multi > 1000000000000000000:
  print("-1")
else:
  print(multi)

### FIXED CODE ###

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

for i in a:
  multi *= i
  if multi > pow(10,18):
    break
if multi > pow(10,18):
  print("-1")
else:
  print(multi)