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

from functools import lru_cache
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


@lru_cache(maxsize=10**6)
def dfs(s, p=-1):
    sub_tree = []
    res = 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        sub_tree.append(size)
        res += size
    if N != res:
        sub_tree.append(N - res)
    memo[s].extend(sub_tree)
    return res


dfs(1)


cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow(2, N - 1, mod) - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow(2, x, mod) - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow(2, N, mod)
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
ans = 0
pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod


def dfs(s, p=-1):
    global ans
    res = 1
    tmp = pow2[N-1] - 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        res += size
        tmp = (tmp - pow2[size] + 1 + mod) % mod
    if N != res:
        tmp = (tmp - pow2[N-res] + 1 + mod) % mod
    ans = (ans + tmp) % mod
    return res


dfs(1)
div = pow2[N]
print(ans*pow(div, mod-2, mod) % mod)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
count=[0]*N
def f(K,L):
  B = L[0:K]+L[K+1:] #popを使うとなぜか元のAまで変化してしまう
  C=list(set(B))
  d = [0]*len(C)
  x=0
  for i in range(len(C)):
    d[i] = int((B.count(C[i]))*(B.count(C[i])-1)/2)
    x += d[i]
  return x


for k in range(N):
  count[k]=f(k,A)

for i in count:
  print(i)

### FIXED CODE ###

import sys
from collections import Counter
N=int(sys.stdin.readline())
L=list(map(int,sys.stdin.readline().split()))
C=Counter(L)
x=0
for a in C.values():
  x += int(a*(a-1)/2)  
for K in range(N):
  print(x-C[L[K]]+1)
### BUGGY CODE ###

import fractions

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

cd = []

for i in range(1, min(A, B) + 1):
    if A % i == 0 and B % i == 0:
        if i % 2 == 0 and i != 2:
            continue
        if i % 3 == 0 and i != 3:
            continue
        if i % 5 == 0 and i != 5:
            continue
        if i % 7 == 0 and i != 7:
            continue
        if i % 11 == 0 and i != 11:
            continue
        if i % 13 == 0 and i != 13:
            continue
        cd.append(i)

l = []

for i in range(0, len(cd)):
    c = cd[i]
    if not l:
        l.append(c)
    else:
        join = True
        for j in range(0, len(l)):
            k = l[j]
            if fractions.gcd(c, k) != 1:
                join = False
                break
        if join:
            l.append(c)

print(len(l))


### FIXED CODE ###

import fractions
import heapq
import itertools


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


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

cd = []
max_cd = fractions.gcd(A, B)

if max_cd == 1:
    cd.append(1)
else:
    heapq.heappush(cd, 1)

    f = [k[0] for k in factorize(max_cd)]
    for v in f:
        heapq.heappush(cd, v)

l = []

for i in range(0, len(cd)):
    c = heapq.heappop(cd)
    if not l:
        l.append(c)
    else:
        join = True
        for j in range(0, len(l)):
            k = l[j]
            if fractions.gcd(c, k) != 1:
                join = False
                break
        if join:
            l.append(c)

print(len(l))
### BUGGY CODE ###


N = int(input())
A = list(map(int,input().split()))
U = [0]*(max(A)+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,max(A)+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,max(A)+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,10**6+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)
### BUGGY CODE ###

import re

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = []
r = []
for i in range(Q):
    l_i, r_i = [int(item) for item in re.split(r"\s", input())]
    l.append(l_i)
    r.append(r_i)

# ACの場所を探す
p_list = []
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list.append(1)
        p_list.append(0)
        i += 2
    else:
        p_list.append(0)
        i += 1

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1
    out_list.append(str(sum(p_list[l_i:r_i])))

print("\n".join(out_list))


### FIXED CODE ###

import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]

# ACの場所を探す
p_list = [0] * (N + 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i + 1] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1

    if l_i >= 0:
        c_l = cumsum[l_i]
    else:
        c_l = 0
    c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

print("\n".join(out_list))
### BUGGY CODE ###

N = int(input())
total = 0

for i in range(N):
    total += i
print(total)

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

import itertools

def main():
    N, K = map(int, input().split())
    h = []
    for i in range(N):
        h.append(int(input()))
    arr = list(itertools.permutations(h, K))
    res1 = []
    res2 = []
    ans = []
    for j in range(len(arr)):
        res1.append(sorted(arr[j]))

    for k in range(len(res1)):
        res2.append(sorted(res1[k]))

    for l in range(len(res2)):
        ans.append(res2[l][K-1] - res2[l][0])
    print(min(ans))
main()


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]

sorted_a = sorted(a)
for value in sorted_a:
    print(a.index(value) + 1, end=' ')
print()


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split(' ')]

dict = {}
for i, value in enumerate(a):
    dict[value] = i + 1

a.sort()

for i in a:
    print(dict[i], end=' ')
print()
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

import numpy as np

n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))


def bfs():
    d = ((1, 0), (0, 1))
    maze = [[0] * (m + 1) for _ in range(n + 1)]
    q = deque([])
    q.append((0, 0))
    maze[0][0] = k
    while q:
        x, y = q.popleft()
        if maze[x][y] < 0:
            for i in range(x, n + 1):
                for j in range(y, m + 1):
                    maze[i][j] = -1
        for i in range(2):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx <= n and 0 <= ny <= m and maze[nx][ny] == 0:
                q.append((nx, ny))
                maze[nx][ny] = maze[x][y] - a[nx] * d[i][0] - b[ny] * d[i][1]
    o = np.array(maze)
    o = np.argwhere(o >= 0)
    return max(sum(i) for i in o)


print(bfs())


### FIXED CODE ###

#!/usr/bin/env python3
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = [0]
B = [0]
for i in range(n):
    A.append(A[i] + a[i])
for i in range(m):
    B.append(B[i] + b[i])
ans = 0
j = m
for i in range(n + 1):
    if A[i] > k:
        break
    while j > 0 and k - A[i] < B[j]:
        j -= 1
    ans = max(ans, i + j)

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

import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))

##### main #####

def is_prime(n):
    i=2
    while i*i <= n:
        if n%i == 0:
            return False
        i+=1
    return n != 1


def main():
	n = I()
	memo = {}
	for i in range(n):
		l,r = LI()
		x=0
		for j in range(l,r+1,2):
			if j in memo:
				if memo[j] == True:
					x+=1
			else:
				jj = (j+1)/2
				if is_prime(j) and is_prime(jj):
					memo[j] = True
					x+=1
				else:
					memo[j] = False
		print(x)



if __name__ == '__main__':
	main()

### FIXED CODE ###

import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))

##### main #####

def primes(max_number):
    """
    指定値未満の素数を取得するジェネレータ
    https://qiita.com/Mokkeee/items/93b6b7d59fa256aa1677
    """
    if max_number <= 2:
        raise StopIteration
    yield 2
    is_prime = [1] * max_number
    square_root_of_max = max_number ** 0.5
    for number in range(3, max_number, 2):
        if is_prime[number] is 0:
            continue
        yield number
        if number <= square_root_of_max:
            for multiple in range(number * 2, max_number, number):
                is_prime[multiple] = 0

def main():
	P = list(primes(10**5))
	P = [p for p in P[1:] if (p+1)//2 == P[bisect_left(P, (p+1)//2)]]
	n = I()

	for i in range(n):
		l, r = LI()
		a = bisect_left(P,l)
		b = bisect_right(P,r)
		print(b-a)


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

import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = []
s_N = []
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        if i[1] in s_N:
            print("POSSIBLE")
            sys.exit()
        s_1.append(i[1])
    if i[1] == N:
        if i[0] in s_1:
            print("POSSIBLE")
            sys.exit()
        s_N.append(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")
    



### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = set()
s_N = set()
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        if i[1] in s_N:
            print("POSSIBLE")
            sys.exit()
        s_1.add(i[1])
    if i[1] == N:
        if i[0] in s_1:
            print("POSSIBLE")
            sys.exit()
        s_N.add(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
AB = [a + b for a in A for b in B]
AB.sort()
AB.reverse()
ABC = [ab + c for ab in AB for c in C]
ABC.sort()
ABC.reverse()
for k in range(K):
    print(ABC[k])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()), reverse=True)
*B, = sorted(map(int, input().split()), reverse=True)
*C, = sorted(map(int, input().split()), reverse=True)
AB = [A[x] + B[y] for y in range(Y) for x in range(X)]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [AB[x] + C[z] for z in range(Z) for x in range(len(AB))]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])
### BUGGY CODE ###

import heapq
import numpy

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

totalCost = numpy.zeros((n,), dtype = int)
totalCost += Yen(s)
totalCost += Snuuk(t)

print(ini - numpy.min(totalCost))
for i in range(1, n):
    print(ini - numpy.min(totalCost[i:n]))

### FIXED CODE ###

import heapq

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

Yen, Snuuk = Yen(s), Snuuk(t)
total, minCost = [], []
tempmin = float("inf")
for i in reversed(range(n)):
    total.append(Yen[i] + Snuuk[i])
    tempmin = min(tempmin, Yen[i] + Snuuk[i])
    minCost.append(tempmin)

for i in reversed(range(n)):
    print(ini - minCost[i])
### BUGGY CODE ###

def main():
    n = input()
    a = input().split(" ")
    r = [str(a.index(str(i+1)) + 1) for i in range(len(a))]
    print(" ".join(r))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.readline

def main():
    n = input()
    a = input().split(" ")
    # r = ""
    # for i in range(int(n)):
    #     r += str(a.index(str(i+1)) + 1) + " "
    # print(r[:-1])
    a = [(a[i],str(i+1)) for i in range(len(a))]
    a = list(map(lambda x:x[1],sorted(a,key=lambda x:int(x[0]))))
    print(" ".join(a))

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

import sys
input = sys.stdin.readline

x = int(input())
li = list(map(int, input().split()))

a = 0 # カウントする

for i in range(len(li)):
    c = 0
    j = 0
    while i >= j:
        if li[i] <=  li[j]:
            c += 1
            if c == i+1:
                a += 1
        j+=1
print(a)

### FIXED CODE ###


x = int(input())
li = list(map(int, input().split()))

a = 0
Min = li[0]
for i in range(len(li)):
    if li[i] <= Min:
        Min = li[i]
        a += 1
print(a)
### BUGGY CODE ###

def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cost=[0,2,5,5,4,5,6,3,7,6]
    dp=[0]*(n+10)
    ans=[]
    for i in range(n+1):
        for j in a:
            dp[i+cost[j]]=max(dp[i]+1,dp[i+cost[j]])
    cnt=n
    while cnt>0:
        for j in a:
            if dp[cnt]==1:
                if cost[j]==cnt:
                    ans.append(j)
                    cnt-=cost[j]
                    break
            elif dp[cnt-cost[j]]==dp[cnt]-1:
                ans.append(j)
                cnt-=cost[j]
                break
    print(''.join(map(str,ans)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

A.sort()
A.reverse()

match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-N-N] * (N + 1)
dp[0] = 0

for i in range(1, N + 1):
  for j in A:
    if i >= match[j]:
      dp[i] = max(dp[i], dp[i - match[j]] + 1)

max_list = []
while N:
  for j in A:
    if N >= match[j] and dp[N] == dp[N - match[j]] + 1:
      max_list.append(j)
      N -= match[j]
      break

for j in max_list:
  print(j, end="")
print("")
### BUGGY CODE ###

N,K=map(int,input().split())
L=[]
for i in range(N):
    s,d=map(int,input().split())
    L.append([s,d])

High=10**30
Low =0
for i in range(500):
    Mid=(High + Low)/2
    cnt=0
    for j in range(N):
        cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    elif cnt<K:
        Low = Mid
    #print(Mid)
import math
print(math.ceil(Mid))

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[]
for i in range(N):
    s,d=map(int,input().split())
    L.append([s,d])

High=10**20
Low =0
while High - Low >1:
    Mid=(High + Low)//2
    cnt=0
    for j in range(N):
        if Mid-L[j][0]<0:
            continue
        else:
            cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    else:
        Low = Mid
    #print(High , Low)
Mid=int(Mid)
ans=0
for j in range(N):
    ans+=max(0,1+(Mid - L[j][0])//L[j][1])
if ans>=K:
    print(Mid)
else:
    print(Mid+1)
### BUGGY CODE ###

r1,c1,r2,c2 = map(int,input().split())

MOD = 10**9+7
def inv(n):
    return pow(n,MOD-2,MOD)

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(r):
        ret *= (n-i)
        ret *= inv(i+1)
    ret %= MOD
    return ret

ans = 0
a = comb(r1+c1-1, r1)
b = comb(r1+c2, r1)
for r in range(r1,r2+1):
    iv = inv(r+1)
    a *= (r+c1) * iv
    b *= (r+c2+1) * iv
    ans += b-a
ans %= MOD
print(ans)

### FIXED CODE ###

r1,c1,r2,c2 = map(int,input().split())

MOD = 10**9+7
MAXN = 2*10**6+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for r in range(r1,r2+1):
    ans += ncr(r+c2+1, r+1) - ncr(r+c1, r+1)
ans %= MOD
print(ans)
### BUGGY CODE ###

from collections import defaultdict
MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 100

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        if (visited[pos] != -INF):
            if (visited[pos] >= cost):
                continue
            if (update_cnt[pos] >= MAX_N):
                continue
            visited[pos] = cost
            update_cnt[pos] += 1
        else:
            visited[pos] = cost
            update_cnt[pos] += 1

        if (pos == N - 1):
            result = max(result, cost)

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]
            que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (result, True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

x=int(input())
i=1
while x!=0:
    print("Case {}:{}".format(i,x))
    i+=1

### FIXED CODE ###

x=int(input())
i=1
while x!=0:
    print("Case %d: %s" %(i,x))
    x=int(input())
    i+=1