Harryxun/stf_run huggingface dataset:
from sys import stdin

INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

n = int(stdin.readline())
M = [[INFTY] * n for i in range(n)]

for u in range(n):
    U = list(map(int, stdin.readline().split()[2:]))
    for j in range(0, len(U), 2):
        M[u][U[j]] = U[j+1]

d = [INFTY for i in range(n)]
color = [WHITE for i in range(n)]

def dijkstra():
    global n
    d[0] = 0
    color[0] = GRAY
    while(1):
        minv = INFTY
        u = -1
        for i in range(n):
            if (minv > d[i] and color[i] != BLACK):
                u = i
                minv = d[i]
        if (u == -1):
            break
        color[u] = BLACK
        for v in range(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if(d[v] > d[u] + M[u][v]:)
                    d[v] = d[u] + M[u][v]
                    color[v] = GRAY
    for i in range(n):
        print(i, (-1 if d[i] == INFTY else d[i]))
dijkstra()

### FIXED CODE ###

from sys import stdin

INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

n = int(stdin.readline())
M = [[INFTY for i in range(n)] for j in range(n)]

for u in range(n):
    U = list(map(int, stdin.readline().split()[2:]))
    for j in range(0, len(U), 2):
        M[u][U[j]] = U[j+1]

d = [INFTY for i in range(n)]
color = [WHITE for i in range(n)]

def dijkstra():
    global n
    d[0] = 0
    color[0] = GRAY
    while(1):
        minv = INFTY
        u = -1
        for i in range(n):
            if (minv > d[i] and color[i] != BLACK):
                u = i
                minv = d[i]
        if (u == -1):
            break
        color[u] = BLACK
        for v in range(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if(d[v] > d[u] + M[u][v]):
                    d[v] = d[u] + M[u][v]
                    color[v] = GRAY
    for i in range(
n):
        print(i, (-1 if d[i] == INFTY else d[i]))
dijkstra()
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


M = 10**9+7
n = int(input())
p = list(map(int, input().split()))
g1 = [None]*(n+10)
v = 1
g1[0] = 1
for i in range(1,len(g1)):
    v *= i
    v %= M
    g1[i] = v
    
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


index = [i for i,num in enumerate(p) if num==0]
used = [False]*n
for i in range(n):
    if p[i]>0:
        used[p[i]-1] = True
nl = []
for i in range(n):
    if not used[i]:
        nl.append(i+1)
nl.sort()
scores = [0]*(n+1) # scores[i]: nlのうちiより大きいものの個数
v = len(nl)
cur = 0
for i in range(1,n+1):
#    if nl and cur<len(nl) and nl[cur]<i:
    if nl and nl[cur]<i:
        cur += 1
        v -= 1
    scores[i] = v
ans = 0
bit = [0]*(n+1)
s = set(index)
val = 0
pp = len(index) # 欠損の個数
ss = sum(nl)
num = 0
inv2 = pow(2, M-2, M)
for i in range(n):
    if i in s:
        ans += (g1[pp-1] * (ss - pp - val - pp*(num)*inv2)) * g1[n-i-1]
        num += 1
    else:
        ans += (g1[pp] * (p[i]-query(bit, p[i])-1) - g1[pp-1]*num*(len(nl)-scores[p[i]])) * g1[n-i-1]
        add(bit, p[i], 1)
        val += scores[p[i]]
    ans %= M
#     print(ans, val)
print((ans + g1[pp])%M)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


M = 10**9+7
n = int(input())
p = list(map(int, input().split()))
g1 = [None]*(n+10)
v = 1
g1[0] = 1
for i in range(1,len(g1)):
    v *= i
    v %= M
    g1[i] = v
    
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


index = [i for i,num in enumerate(p) if num==0]
used = [False]*n
for i in range(n):
    if p[i]>0:
        used[p[i]-1] = True
nl = []
for i in range(n):
    if not used[i]:
        nl.append(i+1)
nl.sort()
scores = [0]*(n+1) # scores[i]: nlのうちiより大きいものの個数
v = len(nl)
cur = 0
for i in range(1,n+1):
    if nl and cur<len(nl) and nl[cur]<i:
#     if nl and nl[cur]<i:
        cur += 1
        v -= 1
    scores[i] = v
ans = 0
bit = [0]*(n+1)
s = set(index)
val = 0
pp = len(index) # 欠損の個数
ss = sum(nl)
num = 0
inv2 = pow(2, M-2, M)
for i in range(n):
    if p[i]==0:
        ans += (g1[pp-1] * (ss - pp - val - pp*(num)*inv2)) * g1[n-i-1]
        num += 1
    else:
        ans += (g1[pp] * (p[i]-query(bit, p[i])-1) - g1[pp-1]*num*(len(nl)-scores[p[i]])) * g1[n-i-1]
        add(bit, p[i], 1)
        val += scores[p[i]]
    ans %= M
#     print(ans, val)
print((ans + g1[pp])%M)
N,Y = map(int,input().split())
x = y = z = 0
for i in range(N,-1,-1):
    if i*10000 <= Y:
        charge = Y - i*10000
        rest = N - i
        for j in range(rest,-1,-1):
            if j*5000 <= charge:
                if charge - j*5000 - (rest-j)*1000 == 0:
                    print('{1} {2} {3}'.format(i, j ,rest-j))
                    exit(0)
print('-1 -1 -1')


### FIXED CODE ###

N,Y = map(int,input().split())
x = y = z = 0
for i in range(N,-1,-1):
    if i*10000 <= Y:
        charge = Y - i*10000
        rest = N - i
        for j in range(rest,-1,-1):
            if j*5000 <= charge:
                if charge - j*5000 - (rest-j)*1000 == 0:
                    print('{0} {1} {2}'.format(i, j ,rest-j))
                    exit(0)
print('-1 -1 -1')
s = input()
l = len(s)

def df(s):
  while True:
    if '01' in s or '10' in s:
      s = s.replace('01', '')
      s = s.replace('10', '')
    else:
      break
  return s

if len(s) < 1000:
  print(l - len(df(s)))
else:
  i = l // 4
  sx = df(s[:i]) + df[i:i * 2] + df[i * 2:i * 3] + df[i * 3:]
  print(l - len(df(sx)))

### FIXED CODE ###

s = input()
print(2 * min([sum([v == '1' for v in s]), sum([v == '0' for v in s])]))
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x
visit = [0 for _ in range(n)]
def add(num):
    if visit[num] == 1:
        return 0
    visit[num] = 1
    for k in inf[num]:
        if visit[k] == 0:
            point[k] += point[num]
            add(k)
        else:
            continue
    return 0
add(0)
print(' '.join(map(str, point)))

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
WeatherToady = input("")
if WeatherToday == "Sunny":
  return "Cloudy"
elif WeatherToday == "Cloudy":
  return "Rainy"
else:
  return "Sunny"


### FIXED CODE ###

WeatherToday = input()
if WeatherToday == "Sunny":
  print("Cloudy")
elif WeatherToday == "Cloudy":
  print("Rainy")
else:
  print("Sunny")
N,M=map(int,input().split())
if(N>M):
    print("safe")
else if(N<=M):
    print("unsafe")

### FIXED CODE ###

N,M=map(int,input().split())
if(N>M):
    print("safe")
elif(N<=M):
    print("unsafe")
import sys

N = int(input())
XY = list()
for i in range(N):
    XY.append(list(map(int, input().split(" "))))

eo = sum(XY[0]) % 2
for xy in XY:
    if (sum(xy) % 2 != eo):
        print(-1)
        os.exit()

m = 40 - eo
print(m)
D = [2 ** i for i in range(38, -1, -1)]
if eo == 0:
    D.append(1)

print(" ".join(map(str, D)))
for x, y in XY:
    w = ""
    for i in range(m):
        if 0 <= x - y and 0 <= x + y:
            w += "R"
            x -= D[i]
        elif 0 > x - y and 0 <= x + y:
            w += "U"
            y -= D[i]
        elif 0 <= x - y and 0 > x + y:
            w += "D"
            y += D[i]
        else:
            w += "L"
            x += D[i]
    print(w)


### FIXED CODE ###

import sys

N = int(input())
XY = list()
for i in range(N):
    XY.append(list(map(int, input().split(" "))))

eo = sum(XY[0]) % 2
for xy in XY:
    if (sum(xy) % 2 != eo):
        print(-1)
        sys.exit()

m = 40 - eo
print(m)
D = [2 ** i for i in range(38, -1, -1)]
if eo == 0:
    D.append(1)

print(" ".join(map(str, D)))
for x, y in XY:
    w = ""
    for i in range(m):
        if 0 <= x - y and 0 <= x + y:
            w += "R"
            x -= D[i]
        elif 0 > x - y and 0 <= x + y:
            w += "U"
            y -= D[i]
        elif 0 <= x - y and 0 > x + y:
            w += "D"
            y += D[i]
        else:
            w += "L"
            x += D[i]
    print(w)
n,m = int(input().split())
k = (n-1)*(m-1)
print(k)

### FIXED CODE ###

n,m = map(int,input().split())
k = (n-1)*(m-1)
print(k)
def cubic(x):
    x = x^3
    print(x\n)

### FIXED CODE ###

x = int(input())
y = x **3
print(y, end = "\n")
n = int(input())
count_dict = {}
for _ in range(n):
    e = input()
    if e in count_dict.keys():
        count_dict[e] += 1
    else:
        count_dict[e] = 0

max_list = [e[0] for e in count_dict.items() if e[1] == max(count_dict.values())]
max_list.sort()
for i in max_list:
    print(i)

### FIXED CODE ###

import sys
input_array = [str(e) for e in input().split()]
for i in set(input_array):
    if input_array.count(i) == 2:
        print('Yes')
        sys.exit()
    else:
        pass
print('No')
N,Q = map(int,input().split())
 
AB = [[int(x) for x in input().split()] for _ in range(N-1)] 
PX = [[int(x) for x in input().split()] for _ in range(Q)]

ki = [[]for _ in range(N+1)]
for a,b in AB:
    a-=1
    b-=1
    ki[a].append(b)
    ki[b].append(a)
point = [0]*N
for p,x in PX:
    p-=1
    point[p]+=x
def dfs(now, last ,add):
    point[now]+= add
    for x in ki[now]:
        if (x == last):continue
        dfs(x,now,point[now])
dfs(0,0,0)
print(*point)
    
    

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N,Q = map(int,input().split())
 
AB = [[int(x) for x in input().split()] for _ in range(N-1)] 
PX = [[int(x) for x in input().split()] for _ in range(Q)]

ki = [[]for _ in range(N)]
for a,b in AB:
    a-=1
    b-=1
    ki[a].append(b)
    ki[b].append(a)
point = [0]*(N)
for p,x in PX:
    p-=1
    point[p]+=x
def dfs(now, last ,add):
    point[now]+= add
    for x in ki[now]:
        if (x == last):continue
        dfs(x,now,point[now])
dfs(0,0,0)
print(*point)
A, B, C, D = [int(x) for x in stdin.readline().rstrip().split()]

if A*B >= C*D:
  print (A*B)
else:
  print (C*D)

### FIXED CODE ###

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

ab = a * b
cd = c * d

if ab == cd:
    print(int(ab))
elif ab > cd:
    print(int(ab))
else:
    print(int(cd))
a, b, t = map(int, input.split())
ans = 0
for i in range(a, t+1):
  ans += b
print(ans)

### FIXED CODE ###

a, b, t = map(int, input().split())
print(t//a*b)
while True:
	sousa=input().sprit() #?????????
	sousa=[int(sousa[0]),int(sousa[1])]
	if sousa==[0,0]:break
	yama=[]
	for k in range(sousa[0]):yama.append(k+1)
	yama=yama[::-1]
	for r in range(sousa[1]):
		[p,c]=input().sprit()
		[p,c]=[int(p),int(c)]
		yama[:p+c-1]=yama[p-1:p+c-1]+yama[:p-2]
	print(yama[0])

### FIXED CODE ###

while True:
	sousa=input().split()
	sousa=[int(sousa[0]),int(sousa[1])]
	if sousa==[0,0]:break
	yama=[]
	for k in range(sousa[0]):yama.append(k+1)
	yama=yama[::-1]
	for r in range(sousa[1]):
		[p,c]=input().split()
		[p,c]=[int(p),int(c)]
		yama[:p+c-1]=yama[p-1:p+c-1]+yama[:p-1]
	print(yama[0])
a=input()
b=input()
c=input()
if a==b:
  print(int(c))
elif a==c:
  print(int(b))
elif b==c:
  print(int(a))

### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b:
    print(c)
elif b==c:
  print(a)
else:
  print(b)
while True:
    (m, f, r) = [int(i) for i in input().split()]
    if m == f == r == -1:
        break
    total = m + f
    if m == -1 or f == -1  or total < 30:
        print('F')
    elif total < 50 and r < 50:
        print('D')
    elif total < 65:
        print('C')
    elif total < 80:
        print('B'):
    else:
        print('A')

### FIXED CODE ###

while True:
    (m, f, r) = [int(i) for i in input().split()]
    if m == f == r == -1:
        break
 
    total = m + f
    if m == -1 or f == -1 or total < 30:
        print('F')
    elif total < 50 and r < 50:
        print('D')
    elif total < 65:
        print('C')
    elif total < 80:
        print('B')
    else:
        print('A')
import map
n, a, b = map(int, raw_input().split())
if a < b:
  max_value = b
else:
  max_value = a

print(str(max_value*n))


### FIXED CODE ###

n, a, b = map(int, raw_input().split())
if a*n > b:
  min_value = b
else:
  min_value = a*n

print str(min_value)
n = int(input())
lis = list(map(int,input().split()))
ans = 0
for i in range(1,n-1):
  lis = sorted([lis[i-1],lis[i],lis[i+1]])
  if lis[1] == lis[i]:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
ans = 0
for i in range(1,n-1):
  li = sorted([lis[i-1],lis[i],lis[i+1]])
  if li[1] == lis[i]:
    ans += 1
print(ans)
from sys import stdin

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

a=p[0]
cnt=1

for i in range(1,n):
    if p[i]<=a
    cnt+=1
    a = p[i]

print(cnt)
      

### FIXED CODE ###

from sys import stdin

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

a=p[0]
cnt=1

for i in range(1,n):
    if p[i]<a:
        cnt+=1
        a = p[i]

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

asum = sum(a)
adic = {}

for i in a:
  if i in adic:
    adic[i] += 1
  else:
    adic[i] = 1


for i in range(q):
  b, c = map(int, input().split())
  if b in adic:
    if c not in adic:
      adic[c] = 0
    cnt = adic.pop(b)
    adic[c] += cnt
  asum += (c-b) * cnt
  print(asum)

### FIXED CODE ###

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

asum = sum(a)
adic = {}

for i in a:
  if i in adic:
    adic[i] += 1
  else:
    adic[i] = 1


for i in range(q):
  b, c = map(int, input().split())
  if b in adic:
    if c not in adic:
      adic[c] = 0
    cnt = adic.pop(b)
    adic[c] += cnt
    asum += (c-b) * cnt
  print(asum)
second=input()
first=spit(second)
P=string(first[0])
S=string(first[1])
count=0
for t in range(0,len(P)-1):
  if P[t]=S[t]:count=count+1
    else count=count
print(int(count))

### FIXED CODE ###

a=[input() for i in range(2)]
P=a[0]
S=a[1]
count=0
for t in range(len(P)):
  if P[t] != S[t]:
    count=count+1
print(count)
import math

N = int(input())

P = list(map(int,input().split()))
Q = list(map(int,input().split()))

def check(A):
    L = [j+1 for j in range(N)]
    ans = 0
    for i in range(N):
        a = L.index(A[i])
        ans += a*math.factorial(N-1-i)
        L.pop(a)
    return ans
p = check(P)
q = check(Q)
print(math.abs(P-Q))

### FIXED CODE ###

import math

N = int(input())

P = list(map(int,input().split()))
Q = list(map(int,input().split()))

def check(A):
    L = [j+1 for j in range(N)]
    ans = 0
    for i in range(N):
        a = L.index(A[i])
        ans += a*math.factorial(N-1-i)
        L.pop(a)
    return ans
p = check(P)
q = check(Q)
print(abs(p-q))
def solve(string):
    ins = string.split("\n")
    h, w = map(int, ins[0].split(" "))
    a = [list(map(int, _i.split(" "))) for _i in ins[1:]]
    curr_x = curr_y = 0
    move_x = 1
    move_y = 0
    move = []
    coordinate_order = []
    check_mat = [[True for _ in range(w)] for _ in range(h)]
    for i in range(h * w):
        coordinate_order.append((curr_y, curr_x))
        if curr_x + move_x < 0 or w - 1 < curr_x + move_x or not check_mat[curr_y][curr_x +
                                                                                   move_x]:
            move_x, move_y = move_y, move_x
        if curr_y + move_y < 0 or h - 1 < curr_y + move_y or not check_mat[curr_y +
                                                                           move_y][curr_x]:
            move_x, move_y = -move_y, -move_x
        check_mat[curr_y][curr_x] = False
        curr_x += move_x
        curr_y += move_y
    for (_cy, _cx), (_ny, _nx) in zip(coordinate_order, coordinate_order[1:]):
        if a[_cy][_cx] % 2 == 0:
            continue
        a[_cy][_cx] -= 1
        a[_ny][_nx] += 1
        move.append("{} {} {} {}".format(_cy + 1, _cx + 1, _ny + 1, _nx + 1))
        return "{}\n{}".format(len(move), "\n".join(move)) if len(move) > 0 else "0"


if __name__ == '__main__':
    line = input()
    tmp = [line]
    for _ in range(int(line[0])):
        tmp.append(input())
    print(solve('\n'.join(tmp)))


### FIXED CODE ###

h,w = map(int,input().split())
a = []
for i in range(h):
    tmp = list(map(lambda x:int(x)%2,input().split()))
    a.append(tmp)
result = []
 
for i in range(h):
    for j in range(w-1):
        if a[i][j] == 1:
            #a[i][j] == 0
            a[i][j+1] = 1 ^ a[i][j+1]
            result.append((i+1,j+1,i+1,j+2)) 
for i in range(h-1):
    if a[i][w-1] == 1:
        a[i+1][w-1] = 1 ^ a[i+1][w-1]
        result.append((i+1,w,i+2,w))
print(len(result))
for row in result:
    print("{} {} {} {}".format(row[0],row[1],row[2],row[3]))
n, M = map(int, input().split())
a = list(map(float, input().split()))
A = sum(a) / (4 * M)
N = sum(x >= A for x in a)
print('Yes' if N >= m else 'No')

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(float, input().split()))
A = sum(a) / (4 * m)
N = sum(x >= A for x in a)
print('Yes' if N >= m else 'No')
import math

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

A.sort()
#print(math.gcd(6, 7))
if N >= 3:
    ans = max(math.gcd(A[0], A[1]), math.gcd(A[1], A[2]), math.gcd(A[0], A[2]))
elif N == 2:
    ans = max(A[0], A[1])
else:
    ans = 1000000000

print(ans)

### FIXED CODE ###

import fractions


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

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
    gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))
import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    print("----")
    cnt = 0
    Flag = True
    while Flag:
        print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    #print("----")
    cnt = 0
    Flag = True
    while Flag:
        #print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))
a,b,t=map(int,input(),split())
print(((t+1/2)//a)*b)


### FIXED CODE ###

a,b,t=map(int,input().split())
print(((t+1//2)//a)*b)
import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
ans=0
root=[i for i in range(n)]
rank=[0]*(n+1)
def find(x):
  if root[x]==x:
    return x
  root[x]=find(root[x])
  return root[x]
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  x=find(x)
  y=find(y)
  if rank[x]>=rank[y]:
    root[y]=x
  else:
    root[x]=y
  if rank[x]==rank[y]:
    rank[x]+=1
def dfs(i,flag):
  if str(flag).count(1)!=n-1:
    if i==m:
      return 0
    dfs(i+1,flag|2**i)
    dfs(i+1|flag)
  root=[i for i in range(n)]
  rank=[0]*(n+1)
  for j in range(m):
    if flag&2**j>0:
      union(number[j][0],number[j][1])
  for j in range(1,n):
    if check(i,i+1)==False:
      return 0
  ans+=1
dfs(0,0)
print(ans)

### FIXED CODE ###

import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
visit=[0]*(n+1)
visit[1]=1
node=[[] for i in range(n+1)]
for i in number:
  node[i[0]].append(i[1])
  node[i[1]].append(i[0])
ans=0
def dfs(x):
  global ans
  if visit.count(1)==n:
    ans+=1
    return 0
  for i in node[x]:
    if visit[i]==0:
      visit[i]=1
      dfs(i)
      visit[i]=0
  return 0
dfs(1)
print(ans)
N = input()
n = N[len(N)]
if n == "2" or n== '4' or n=='5' or n=='7' or n=='9':
  print("hon")
elif n == '0' or n=='1' or n=='6' or n=='8':
  print('pon')
else:
  print('bon')

### FIXED CODE ###

N = input()
n = N[len(N)-1]
if n == "2" or n== '4' or n=='5' or n=='7' or n=='9':
  print("hon")
elif n == '0' or n=='1' or n=='6' or n=='8':
  print('pon')
else:
  print('bon')
class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self,gorl):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        self.ans = self.dist[gorl]
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                self.dist[t] = self.dist[f] + cost
        return self.ans if self.ans == self.dist[gorl] else '-inf'

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

bf = BellmanFord(n,0)

for i in range(m):
    a,b,c = map(int,input().split())
    bf.add(a - 1,b - 1,- c)

ans = bf.build()
if ans == '-inf':
    print('inf')
else:
    print(- ans)


### FIXED CODE ###

class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        self.ans = self.dist[n-1]
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                self.dist[t] = self.dist[f] + cost
        return self.ans == self.dist[n-1]

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

bf = BellmanFord(n,0)

for i in range(m):
    a,b,c = map(int,input().split())
    bf.add(a - 1,b - 1,- c)

if bf.build():
    print(- bf.ans)
else:
    print('inf')