Harryxun/stf_run huggingface dataset:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
for i,(c,d)in enumerate(t[m:],1):
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.johnson(csr_matrix((D,(R,C))),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

### FIXED CODE ###

from scipy.sparse import*
n,m,s,*t=map(int,open(0).read().split())
row,col,dat=[],[],[]
for u,v,a,b in zip(*[iter(t[:m*4])]*4):
    for i in range(2501-a):
        row+=(i+a)*51+u,(i+a)*51+v
        col+=i*51+v,i*51+u
        dat+=b,b
for i,(c,d)in enumerate(zip(*[iter(t[m*4:])]*2),1):
    for j in range(2501-c):
        row+=j*51+i,
        col+=(j+c)*51+i,
        dat+=d,
d=csgraph.dijkstra(csr_matrix((dat,(row,col)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(d[i::51].min()))
N,L=map(int,input().split())
s=[list(input()) for i in range(N)]
p=sorted(s)

print("".joint(p))

### FIXED CODE ###

N,L=map(int,input().split())
s=[str(input()) for i in range(N)]
p=sorted(s)
print("".join(p))
a,b,c,d=map(int,input().split())
ans=-999999999999999999
for i in range(a,b+1):
  for j in range(c,d+1):
    ans=max(ans,i*j)

print(ans

### FIXED CODE ###

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

q=a*c
w=a*d
e=b*c
r=b*d

ans=max(q,w,e,r)
print(ans)
s=input()
if int(s[5:7])<5:
	print('Heisei')
else:
	print('TBD')

### FIXED CODE ###

a,b=map(int,input().split())
if b%a==0:
	print(a+b)
else:
	print(b-a)
N = int(input())
H = list(map(int, input().split()))

H = H[::-1]
for i in range(1, N):
    if H[i] > H[i-1] + 1:
        check = 1
        break
    if H[i] > H[i-1]:
        H[i] -= 1

if check:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

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

H = H[::-1]
check = 0
for i in range(1, N):
    if H[i] > H[i-1] + 1:
        check = 1
        break
    if H[i] > H[i-1]:
        H[i] -= 1

if check:
    print('No')
else:
    print('Yes')
S=input()
s=0
for i in range(len(S)):
  if i%2==0:
    if S[i]=="R" or "U" or "D":
      s+=1
  else:
    if S[i]="L" or "U" or "D":
      s+=1
if s==len(S):
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

S=input()
i=0
while i<len(S):
  if i%2==0:
    if S[i]=="L":
      print("No")
      exit()
    else:
      i+=1
  else:
    if S[i]=="R":
      print("No")
      exit()
    else:
      i+=1
print("Yes")
params = input().split(' ')
m = eval(params[0])
n = eval(params[1])

penaltyCount = []

for i in range(m):
    penaltyCount.append(0)

penalties = 0
points = 0

for i in range(n):
    submission = input().split(' ')
    p = eval(submission[0])
    status = submission[1]
    
    if penaltyCount[p] == -1:
        continue

    if status == 'AC':
        penalties += penaltyCount[p]
        penaltyCount[p] = -1
        points += 1
    else:
        penaltyCount[p] += 1


print(points, penalties)


### FIXED CODE ###

params = input().split(' ')
m = eval(params[0])
n = eval(params[1])

penaltyCount = []

for i in range(m):
    penaltyCount.append(0)

penalties = 0
points = 0

for i in range(n):
    submission = input().split(' ')
    p = eval(submission[0])-1
    status = submission[1]
    
    if penaltyCount[p] == -1:
        continue

    if status == 'AC':
        penalties += penaltyCount[p]
        penaltyCount[p] = -1
        points += 1
    else:
        penaltyCount[p] += 1


print(points, penalties)
from collections import Counter
n=int(input())
string_list=[sorted(Counter(input()), key=lambda x:x[0]) for i in range(n)]
cnt=0
for i in range(n):
  si = string_list[i]
  for j in range(i, n):
    sj = string_list[j]
    if si.items() == sj.items():
      cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter
n=int(input())
string_list=["".join(sorted(list(input()))) for i in range(n)]
counter=Counter(string_list)
cnt=0
for k, v in counter.items():
  cnt+=int(v*(v-1)/2)
print(cnt)
def solution(path1, path2, path3):
    counts = [0, 0, 0, 0]
    paths = [path1, path2, path3]
    for path in paths:
        counts[path[0]] += 1
        counts[path[1]] += 1

    countsOfCounts = [0, 0]
    for count in counts:
        if count == 1:
            if countsOfCounts[0] == 2:
                return "NO"
            countsOfCounts[0] += 1
        elif count == 2:
            if countsOfCounts[1] == 2:
                return "NO"
            countsOfCounts[1] += 1
        else:
            return "NO"
    return "YES"


s1, s2, s3 = input().split('\n')
path1 = [int(s) for s in s1.split(' ')]
path2 = [int(s) for s in s2.split(' ')]
path3 = [int(s) for s in s3.split(' ')]

print(solution(path1, path2, path3))


### FIXED CODE ###

def solution(path1, path2, path3):
    counts = [0, 0, 0, 0]
    paths = [path1, path2, path3]
    for path in paths:
        counts[path[0] - 1] += 1
        counts[path[1] - 1] += 1

    countsOfCounts = [0, 0]
    for count in counts:
        if count == 1:
            if countsOfCounts[0] == 2:
                return "NO"
            countsOfCounts[0] += 1
        elif count == 2:
            if countsOfCounts[1] == 2:
                return "NO"
            countsOfCounts[1] += 1
        else:
            return "NO"
    return "YES"


path1 = [int(s) for s in input().split(' ')]
path2 = [int(s) for s in input().split(' ')]
path3 = [int(s) for s in input().split(' ')]

print(solution(path1, path2, path3))
from fractions import Fraction

def main():
    count = int(input())
    number_list = map(int, input().split(' '))

    sum = 0
    for number in number_list:
        sum += Fraction(1, number)

    up, down = map(int, str(sum).split('/'))
    print(down / up)        

if __name__ == "__main__":
    main()

### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    s = input().split()
    sum = 0

    for i in range(N):
        sum = sum + 1/(int(s[i]))
    print(1/sum)
import math
h,w = map(int,(input().split()))
h = math.floor(h)
w = math.floor(w)
sum = h * w

if h == 1 and w ==1:
    print("1")
elif h % 2 == 0:
    result = math.floor(sum /2)
    print(result)
else:
    result = math.floor(sum /2 + 1)
    print(result)

### FIXED CODE ###

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

left = 4 * a * b
d = c -a -b
right =d * d

if d < 0:
    print("No")
elif left < right:
    print("Yes")
else:
    print("No")
import sys
sys.setrecursionlimit(450000)
input = sys.stdin.readline

def Tsundoku(i,j,k,n,m,dp,a,b):
    if dp[i][j]!=None:
        return dp[i][j]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        ans1 = 1+Tsundoku(i+1,j,k-a[i],n,m,dp,a,b)
    if j<m and k-b[j]>=0:
        ans2 = 1+Tsundoku(i,j+1,k-b[i],n,m,dp,a,b)
    dp[i][j] = max(ans1,ans2)
    return dp[i][j]
        
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [[None]*(m+1) for _ in range(n+1)]
ans = Tsundoku(0,0,k,n,m,dp,a,b)
print(ans)

### FIXED CODE ###

from itertools import accumulate

def bs(t):
    l,h = 0,len(b)-1
    while l<=h:
        m = (l+h)//2
        if b[m]<t:
            l=m+1
        elif b[m]>t:
            h=m-1
        else:
            return m
    return h

n,m,k = map(int,input().split())
a = list(accumulate([0]+list(map(int,input().split()))))
b = list(accumulate([0]+list(map(int,input().split()))))
ans = 0
for idx,i in enumerate(a):
    if i<=k:
        #print(idx,bs(k-i))
        ans = max(ans,bs(k-i)+idx)
print(ans)
n,k = map(int , input().split())
l = tuple(map(int , input().split()))
if(k < n):
    dp = [0]*n
    dp[0] = 0
    dp[1] = abs(l[1]-l[0])
    if(n > 2):
        for i in range(2,n):
            min1 = 0
            #print(min1,i)
            for j in range(1,k+1):
                #print(i-j)
                if(i-j >= 0):
                    if(min1 == 0):
                        min1 = dp[i-j]+abs(l[i]-l[i-j])
                        #print(min1,dp[i-j],i-j)
                    else:
                        min1 = min(min1,dp[i-j]+abs(l[i]-l[i-j]))
                        #print(min1)
                else:
                    break
            dp[i] = min1
            #print(dp[i],i)
    
    #print(*dp)
    print(dp[-1])
else:
    print("0")

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
dp = [0 for i in range(n)]
dp[1] = abs(l[1]-l[0])
for i in range(2,n):
    dp[i] = min(dp[i-1] + abs(l[i]-l[i-1]),dp[i-2]+abs(l[i]-l[i-2]))
print(dp[-1])
N, K = map(int, input().split())
S = list(input())

p = 0
while K > 0 and p < len(S):
	now = S[p]
	p += 1
	if p >= len(S):
		break
	while now == S[p]:
		p += 1
		if p >= len(S):
			break

	q = p + 1
	if q >= len(S):
		if S[p] == "R":
			S[p] = "L"
		else:
			S[p] = "R"
		break
	while S[p] == S[q]:
		q += 1
		if q >= len(S):
			break
	while p < q:
		if S[p] == "R":
			S[p] = "L"
		else:
			S[p] = "R"
		p += 1
		if p >= len(S):
			break
	K -= 1

ret = 0;
for x in range(len(S)-1):
	if S[x] == S[x + 1]:
		ret += 1
print(ret)


### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
 
p = 0
while K > 0 and p < len(S):
	now = S[p]
	p += 1
	if p >= len(S):
		break
	while now == S[p]:
		p += 1
		if p >= len(S):
			break
			
	if p >= len(S):
		break
	q = p + 1
	if q >= len(S):
		if S[p] == "R":
			S[p] = "L"
		else:
			S[p] = "R"
		break
	while S[p] == S[q]:
		q += 1
		if q >= len(S):
			break
	while p < q:
		if S[p] == "R":
			S[p] = "L"
		else:
			S[p] = "R"
		p += 1
		if p >= len(S):
			break
	K -= 1
 
ret = 0;
for x in range(len(S)-1):
	if S[x] == S[x + 1]:
		ret += 1
print(ret)
import math
N, K = map(int,input().split())
N = math.gcd(N,K)
for i in range(10*6):
    N = abs(N-K)
    if N == 0:
        break
print(N)

### FIXED CODE ###

#
N, K = map(int,input().split())
N  %= K
min = N
for i in range(10**6):
    N = abs(N-K)
    if min > N:
        min = N
    if N == 0:
        min = 0
        break
print(min)
h, w, d = map(int, input().split())
x = []
z = [[0, 0] for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]
print(z)
s = [0 for _ in range(d)]
for i in range(d):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [0 for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

h, w, d = map(int, input().split())
x = []
z = [None for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]

s = [None for _ in range(d)]
for i in range(min(d, h * w - d + 1)):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [None for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])
N=int(input())
A=list(map(int,input().split()))
 
if 0 in A:
    print(0)
    exit(0)
    
ans = 1 
for i in A:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit(0)
        
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
import math

a, b, x = map(int, input().split())

def calc_theta(a, b, x):
    if x > 0.5 * a ** 2 * b:
        tmp = (a ** 3) / (2 * ((a **2) * b - x))
    else:
        tmp = (2 * x) / ((b ** 2) * a)

    return 90 - math.degrees(math.atan(tmp))

ans = calc_theta(a, b, x)

print(ans)






### FIXED CODE ###

import math

a, b, x = map(int, input().split())

def calc_theta(a, b, x):
    if x >= 0.5 * a ** 2 * b:
        # tmp = (a ** 3) / (2 * ((a **2) * b - x)) これだと 0divになる
        tmp = (2/a)*(b-(x/a**2))
    else:
        tmp = (a * b * b) / (2 * x)
    return math.degrees(math.atan(tmp))

ans = calc_theta(a, b, x)

print('{:.10f}'.format(ans))
n,w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [[float("-inf")]*(w+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    a = wv[i]
    for j in range(w+1):
        if a[0] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j- a[0]] + a[1])
        else:
            dp[i+1][j] = dp[i][j]

print(max(dp[-1]))

### FIXED CODE ###

n,w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

v = sum(list(map(lambda x: x[1], wv)))
dp = [[float("inf")]*(v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    a = wv[i]
    for j in range(v+1):
        if a[1] <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j- a[1]] + a[0])
        else:
            dp[i+1][j] = dp[i][j]

dpl = dp[-1]
for i in range(v, -1, -1):
    if dpl[i] <= w:
        print(i)
        break
import math

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

n = math.factorial(N) / math.factorial(N-2) / 2
m = math.factorial(M) / math.factorial(M-2) / 2

print(int(n + m))

### FIXED CODE ###

import math

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

def f(a):
    if a > 1:
        return int(math.factorial(a) / math.factorial(a-2) / 2)
    else:
        return 0

print(f(N) + f(M))
color = input()
if color >= 3200:
  print(color)
  else:
  print('red')

### FIXED CODE ###

num = int(input())
color = input()
 
if num >= 3200:
  print(color)
else:
  print('red')
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))


ans=0
for i in range(N):
  ans+=B[A[i]-1]
  if(i>=1):
    if(A[i]==A[i-1]+1):
      ans+=C[i]
      
print(ans)
  


### FIXED CODE ###

import math

def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))


    ans=0
    for i in range(N):
        ans+=B[A[i]-1]
        if(i>=1):
            if(A[i]==A[i-1]+1):
                ans+=C[A[i-1]-1]
        
    print(ans)
  

resolve()
#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <cstring>

using namespace std;
typedef long long ll;
typedef pair<char, int> P;

int main() {
    char k[20];
    scanf("%s", k);
    for (int i = 0; i < strlen(k); i++) {
        k[i] = tolower(k[i]);
    }
    int r = 0;
    while (1) {
        char b[1010];
        scanf("%s", b);
        if (!strcmp(b, "END_OF_TEXT")) {
            break;
        }
        char b2[1010];
        int c = 0;
        for (int i = 0; i <= strlen(b); i++) {
            b[i] = tolower(b[i]);
            if (b[i] == ' ' || b[i] == '\0') {
                b2[c] = '\0';
                if (!strcmp(k, b2)) {
                    r++;
                }
                c = 0;
            } else {
                b2[c] = b[i];
                c++;
            }
            if (b[i] == '\0') break;

        }
    }
    printf("%d\n", ra);
    return 0;
}

### FIXED CODE ###

import sys
k = raw_input().lower()
l = []
for s in sys.stdin:
    if s == 'END_OF_TEXT':
        break
    l += [t.lower() for t in s.strip().split(' ')]
print(l.count(k))
#4
n,k=map(int,input().split())
s=str(input())

import numpy as np
line = np.zeros([2*n,],dtype=np.int)
counter1 = 0
counter0 = 0
ind = 0
for i in range(n):
    c = int(s[i])
    if ind%2 ==0:
        if c == 1:
            counter1 += 1
        else:
            counter0 += 1
            if ind == 0:
                line[ind] = counter1
            else:
                line[ind] = line[ind-1]+counter1
            counter1 = 0
            ind+=1
    elif ind%2 ==1:
        if c == 0:
            counter0 += 1
        else:
            counter1 += 1
            line[ind] = line[ind-1] + counter0
            counter0 = 0
            ind+=1

if ind%2 ==0:
        if ind == 0:
                line[ind] = counter1
        else:
                line[ind] = line[ind-1]+counter1
        ind+=1
elif ind%2 ==1:
        line[ind] = line[ind-1] + counter0
        ind+=1
        

line[1:ind+1]  = line[:ind]   
line[0] = 0 
line = line[:ind+1]
#print(line)

if (len(line)//2)<=k:
    print(n)
else:
    maxchain = 0
    for i in range(0,len(line)-(2*k+1)+1,2):
        chain = line[i+2*k+1]-line[i]
        #print(chain)
        if chain>maxchain:
            maxchain=chain
    print(maxchain)

### FIXED CODE ###

#4
n,k=map(int,input().split())
s=str(input())

import numpy as np
line = np.zeros([2*n,],dtype=np.int)
counter1 = 0
counter0 = 0
ind = 0
for i in range(n):
    c = int(s[i])
    if ind%2 ==0:
        if c == 1:
            counter1 += 1
        else:
            counter0 += 1
            if ind == 0:
                line[ind] = counter1
            else:
                line[ind] = line[ind-1]+counter1
            counter1 = 0
            ind+=1
    elif ind%2 ==1:
        if c == 0:
            counter0 += 1
        else:
            counter1 += 1
            line[ind] = line[ind-1] + counter0
            counter0 = 0
            ind+=1

if ind%2 ==0:
        if ind == 0:
                line[ind] = counter1
        else:
                line[ind] = line[ind-1]+counter1
        ind+=1
elif ind%2 ==1:
        line[ind] = line[ind-1] + counter0
        ind+=1
        
if ind%2 ==0:
        line[ind] = line[ind-1]
        ind+=1
        
line[1:ind+1]  = line[:ind]   
line[0] = 0 
line = line[:ind+1]
#print(line)

if (len(line)//2)<=k:
    print(n)
else:
    maxchain = 0
    for i in range(0,len(line)-2*k,2):
        chain = line[i+2*k+1]-line[i]
        #print(chain)
        if chain>maxchain:
            maxchain=chain
    print(maxchain)
import collections
n,x,m=map(int,input().split())
start,end,loopcnt=0,0,0
a={x:0}
wk=x
for i in range(1,m):
  wk=(wk*wk)%m
  if not wk in a:
    a[wk]=i
  else:
    start=a[wk]
    end=i
    break
a=sorted(a.items(),key=lambda x:x[1])
koteiindex=min(n,start)
koteiwa=0
for i in range(koteiindex):
  koteiwa+=a[i][0]
loopcnt=(n-koteiindex)//(end-start)
loopindex=(n-koteiindex)%(end-start)
loopwa=0
amariwa=0
for i in range(start,end):
  if i<=loopindex+1:
    amariwa+=a[i][0]
  loopwa+=a[i][0]
ans=koteiwa+loopwa*loopcnt+amariwa
print(ans)


### FIXED CODE ###

import collections
n,x,m=map(int,input().split())
if n==1 or x==0:
  print(x)
  exit()
start,end,loopcnt=0,0,0
a={x:0}
wk=x
for i in range(1,m):
  wk=(wk*wk)%m
  if not wk in a:
    a[wk]=i
  else:
    start=a[wk]
    end=i
    break
a=sorted(a.items(),key=lambda x:x[1])
koteiindex=min(n,start)
koteiwa=0
for i in range(koteiindex):
  koteiwa+=a[i][0]
loopcnt=(n-koteiindex)//(end-start)
loopindex=start-1+(n-koteiindex)%(end-start)
loopwa=0
amariwa=0
for i in range(start,end):
  if i<=loopindex:
    amariwa+=a[i][0]
  loopwa+=a[i][0]
ans=koteiwa+loopwa*loopcnt+amariwa
print(ans)
from queue import deque
def main():
    R, W = "R", "W"
    N = int(input())
    _C = input()
    C = deque(_C)

    count = 0
    while True:
        i = len(C) -1
        while C[i] != R:
            i -= 1
        j = 0
        while C[j] != W:
            j +=1
            if j >= len(C):
                break
        if  i < j:
            break
        C[i], C[j] = C[j], C[i]
        count += 1
    
    print(count)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from queue import deque
def main():
    R, W = "R", "W"
    N = int(input())
    C = input()

    counter = dict()
    for c in C:
        counter[c] = counter.get(c, 0) + 1
    r = counter.get(R, 0)

    _counter = dict()
    for c in C[r:]:
        _counter[c] = _counter.get(c, 0) + 1
    _r = _counter.get(R, 0)

    ans = _r
    print(ans)
if __name__ == '__main__':
    main()
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
import numpy as np

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c

	return passed


connected = dfs(0)
connected_nodes = [i for i, e in enumerate(connected) if e]
new = [-1] * n
for i, e in enumerate(connected_nodes):
	new[e] = i
l = len(connected_nodes)

g2 = [[np.inf] * l for _ in range(l)]
for i, e in enumerate(connected_nodes):
	for j, c in enumerate(g[e]):
		if new[j] != -1:
			g2[e][new[j]] = c


try:
	graph = csr_matrix(g2)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[n-1])
	print(ans)

except:
	print("inf")


### FIXED CODE ###

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)
import math
N,K = map(int, input().split())
a = list(map(int,input().split()))
l = 0
r = K - 1
Min = float("inf")
for i in range(N - K + 1):
    if(a[l]*a[r]<=0):#原点を跨ぐとき
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(l==0):#左端の時
        if(a[r]*a[r+1]<0 or a[0]>0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(r==N-1):#右端の時
        if(a[l-1]*a[l]<0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    else:
        if(a[r]*a[r+1]<0 or a[l-1]*a[l]<0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    l = l + 1
    r = r + 1
print(Min)

### FIXED CODE ###

import math
N,K = map(int, input().split())
a = list(map(int,input().split()))
l = 0
r = K - 1
Min = float("inf")
for i in range(N - K + 1):
    if(a[l]*a[r]<=0):#原点を跨ぐとき
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(l == 0 and r == N-1):
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))        
    elif(l==0):#左端の時
        if(a[r]*a[r+1]<0 or a[0]>0 or (a[N-1]<0 and r == N-1)):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(r==N-1):#右端の時
        if(a[l-1]*a[l]<0 or (a[l]>0 and l == 0) or a[r] <= 0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    else:
        if(a[r]*a[r+1]<0 or a[l-1]*a[l]<0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    l = l + 1
    r = r + 1
print(Min)