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

N = int(input())
l = [(int(input())-1) for _ in range(N)]
flag = [0]*N
flag[0] = 1
flag[1] = 2
cnt = 0
cur_b = 0
while True:
    cnt += 1
    next_b = l[cur_b]
    if flag[next_b] == 1:
        print(-1)
        break
    elif flag[next_b] == 2:
        print(cnt)
        break
    else:
        flag[next_b] == 1
        cur_b = next_b
        

### FIXED CODE ###

N = int(input())
l = [(int(input())-1) for _ in range(N)]
flag = [0]*N
flag[0] = 1
flag[1] = 2
cnt = 0
cur_b = 0
for i in range(N):
    cnt += 1
    next_b = l[cur_b]
    if flag[next_b] == 1:
        print(-1)
        break
    elif flag[next_b] == 2:
        print(cnt)
        break
    else:
        flag[next_b] == 1
        cur_b = next_b
else:print(-1)
### BUGGY CODE ###

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

mod=10**9+7

J=pow(2,n)%mod
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

C=find_inv_power(2*10**5+100)
if  True:
    c=1
    for i in range(a):
        c*=(n-i)
        c=c%mod
    c=c*C[a]
    c=c%mod
    d=1
    for i in range(b):
        d*=(n-i)
        d=d%mod
    d=d%mod
    d=d*C[b]
    print((J-c-d-1)%mod)

### FIXED CODE ###

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

mod=10**9+7
def cal(n):
    if n==1:
        return 2
    else:
        if n%2==0:
            return (cal(n//2)**2)%mod
        elif n%2!=0:
            return ((cal(n//2)*cal(n-n//2))%mod)
J=cal(n)-1
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

C=find_inv_power(2*10**5+100)
if  True:
    c=1
    for i in range(a):
        c*=(n-i)
        c=c%mod
    c=c*C[a]
    c=c%mod
    d=1
    for i in range(b):
        d*=(n-i)
        d=d%mod
    d=d%mod
    d=d*C[b]
    print((J-c-d)%mod)
### BUGGY CODE ###

def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))

    if n <= k:
        print(0)
    elif k > int((n - 1) /2):
        sum_ = sum(a)
        for i in range(n - k):
            a.remove(min(a))
        print(sum_ - sum(a))
    else:
        for i in range(k):
            a.remove(max(a))

        print(sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = list(map(int, input().split()))
    h = list(map(int, input().split()))
    h = sorted(h, reverse=True)

    if n <= k:
        print(0)
    else:
        print(sum(h[k:]))


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

MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 5)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == "?":
        c = -1
    else:
        c = int(s)

    for j in range(10):
        if c != -1 and c != j:
            continue

        for r in range(13):
            dp[i + 1][(r * 10 + j) % 13] += dp[i][r]

        for r in range(13):
            dp[i + 1][r] %= MOD

print(dp[N][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 5)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == "?":
        c = -1
    else:
        c = int(s)

    for j in range(10):
        if c != -1 and c != j:
            continue

        for r in range(13):
            dp[i + 1][(r * 10 + j) % 13] += dp[i][r]

        for r in range(13):
            dp[i + 1][r] %= MOD

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

from collections import deque
from collections import defaultdict
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = deque()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.append([i, j])

def get_unique(q):
    r = deque()
    seen = defaultdict(int)
    for a in q:
        key = str(a[0]) + "-" + str(a[1])
        if seen[key] == 0:
            seen[key] = 1
            r.append(a)
    return r


for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = get_unique(Q)
    Q = deque()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

for i in range(N):
    if len(A[i]) > 0:
        print(-1)
        exit()

print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = set()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.add((i, j))

for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = Q.copy()
    Q = set()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

for i in range(N):
    if len(A[i]) > 0:
        print(-1)
        exit()

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

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

flag = False

for i in range(len(A)):
    for a in A[i+1:]:
        if A[i] == a:
            print('NO')
            flag = True
            break
    if flag:
        break
else:
    print('YES')


### FIXED CODE ###

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

if len(A) == len(set(A)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())
D=int(A*B/math.gcd(A,B))
maxi=0
if D<N:
  for i in range(1,D+1):
    if (i%B)*A/B-(A*i)%B/B>maxi:
      maxi=(i%B)*A/B-(A*i)%B/B
      if maxi==A*(B-1)/B:
        break
else:
  for i in range(1,N+1):
    if (i%B)*A/B-(A*i)%B/B>maxi:
      maxi=(i%B)*A/B-(A*i)%B/B
      if maxi==A*(B-1)/B:
        break
print(int(maxi))

### FIXED CODE ###

import math
A,B,N=map(int,input().split())
D=int(A*B/math.gcd(A,B))
maxi=0
if B-1<=N:
  print(int((B-1)%B*A/B-(A*(B-1))%B/B))
else:
  print(int(N%B*A/B-(A*N)%B/B))
### BUGGY CODE ###

n,m=map(int,input().split())
day_pay=[0 for _ in range(m)]
hikae=[[] for _ in range(m)]
for _ in range(n):
    a,b=map(int,input().split())
    if a>m:
        continue
    if day_pay[a-1]<b:
        hikae[a-1].append(day_pay[a-1])
        day_pay[a-1]=b
    else:
        hikae[a-1].append(b)
for i in hikae:
    i.sort()

ans=0
for d in range(0, m):
    best=max(day_pay[:d+1])
    idx=day_pay[:d+1].index(best)
    try:
        day_pay[idx]=hikae[idx].pop()
    except:
        day_pay[idx]=0
    ans+=best
print(ans)
    


### FIXED CODE ###

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

fee = [[] for _ in range(10**5+10)]  # i日後に収入がもらえるバイトの価値
for _ in range(N):
    a, b = map(int, input().split())
    fee[a].append(-b)

task = []
ans = 0

# 締め切り日からさかのぼっていって、できるバイトで最大の収入をもらえるやつを実行する感じ
for i in range(1, M + 1):
    for f in fee[i]:
        heapq.heappush(task, f)

    if task:
        ans -= heapq.heappop(task)

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

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
time = 0
cnt = 0
C = []
SA =[0]
SB =[0]
for a in A:
    SA.append(SA[-1] + a)
for b in B:
    SB.append(SB[-1] + b)
for x in range(N+1):
    L = K - SA[x]
    if L < 0:
        break
    y_max = 0
    for y in range(M+1):
        T = SB[y]
        if L >= T:
            y_max += 1
        else:
            break
    C.append(y_max - 1 + x)
print(max(C))

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for j in range(M):
    b.append(b[j] + B[j])
j = M
ans = []
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans.append(i + j)
ans_max = max(ans)
print(ans_max)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
a = 1
for i in range(K):
    a *= A[i]
old = a
for i in range(N - K):
    a //= A[i]
    a *= A[K + i]
    ans = 'No'
    if a > old:
        ans = 'Yes'
    print(ans)
    old = a

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N - K):
    ans = 'No'
    if A[i] < A[i + K]:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

sum = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sum += gcd(a,b,c)

print(sum)


### FIXED CODE ###

import math
from functools import reduce
import time

K = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

sum = 0

for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            G = gcd(a,b,c)
            if a == b and b == c:
                sum += G
            elif a == b or b == c:
                sum += G*3
            else:
                sum += G*6

print(sum)
### BUGGY CODE ###

N = int(input())
X = input()

a = int(X, 2)
b = X.count("1")

for i in range(N):
    if X[i] == "1":
        if b == 1:
            print(0)
            continue
        t = (a - pow(2, N-1-i, b-1)) % (b-1)
    else:
        t = (a + pow(2, N-1-i, b+1)) % (b+1)
    
    ans = 1
    while t > 0:
        t %= bin(t).count("1")
        ans += 1
    print(ans)


### FIXED CODE ###

N = int(input())
X = input()

a = int(X, 2)
b = X.count("1")

if b > 1:
    a1 = a % (b-1)
else:
    a1 = 0
a0 = a % (b+1)

for i in range(N):
    if X[i] == "1":
        if b == 1:
            print(0)
            continue
        t = (a1 - pow(2, N-1-i, b-1)) % (b-1)
    else:
        t = (a0 + pow(2, N-1-i, b+1)) % (b+1)
    
    ans = 1
    while t > 0:
        t %= bin(t).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

s = list(input())
q = int(input())
han = False
for i in range(q):
    x = list(input())
    if len(x) == 1:
        if han:
            han = False
        else:
            han = True
        #s.reverse()
    else:
        if han:
            if x[2] == "1":
                s.append(x[4])
            else:
                s.insert(0, x[4])
        else:
            if x[2] == "1":
                s.insert(0, x[4])
            else:
                s.append(x[4])
if han:
    s.reverse()
print("".join(s))

### FIXED CODE ###

s = list(input())
q = int(input())
left = []
right = []
rev = False
for i in range(q):
    x = list(input())
    if len(x) == 1:
        rev = not rev
        #s.reverse()
    else:
        if (x[2] == "1" and not rev) or (x[2] == "2" and rev):
            left.append(x[4])
        else:
            right.append(x[4])
ans = "".join(left[::-1]) + "".join(s) + "".join(right)
if rev:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
a =[int(x) for x in input().split()]
ans = 0
ans2 = 0
b = 10**9 + 7
for index,i in enumerate(a):
    for j in a[index+1:]:
        ans2 = (ans2 + i * j) % b
        ans =  (ans + ((i%b) * j))%b
print(ans)

### FIXED CODE ###

n = int(input())
a_list =[int(x) for x in input().split()]
mod = 10**9 + 7

s_list = [0]*(n+1)
for i,a in enumerate(a_list):
    s_list[i+1] = s_list[i]+a


ans = 0
for i,a in enumerate(a_list):
    ans += a * (s_list[n]-s_list[i+1])
    
print(ans%mod)
### BUGGY CODE ###

from itertools import permutations, combinations, product
import numpy as np

N = int(input())
A = list(map(int, input().split()))
# S = np.array(list(combinations(A,2)))
M = 10**9 + 7
cnt = 0
for i in range(N):
    cnt += A[i] * sum(A[i+1:])
print(cnt%M)



### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
M = 10**9 + 7

S = sum(A)
S2 = sum(map(lambda x: x**2, A))
print(((S**2 - S2)// 2)%M)
### BUGGY CODE ###

n = int(input())

p = [int(input()) for _ in range(n)]


# すでに並んでる列
ordered = []
unordered = []

previous = 0
for i in p:
    if previous < i:
        ordered.append(i)
        previous = i
    else:
        unordered.append(i)
        

count = 0

center = ordered[len(ordered)//2]
unordered.sort(key=(lambda x: abs(x - center)))

for t in unordered:
    count += 1
    index = 0
    if center > t:
        index = 0
        for i in ordered:
            if i < t:
                count +=1
                index +=1
            else:
                break
    else:
        index = -1
        for i in reversed(ordered):
            if i > t:
                count +=1
                index -=1
            else:
                break


    ordered.insert(index, t)

print(count)




### FIXED CODE ###

n = int(input())

p = [int(input()) for _ in range(n)]


# 連続している最大値を求める

lengths = {}
for pn in p:
    if pn in lengths:
        lengths[pn+1] = lengths[pn] + 1
    else:
        lengths[pn+1] = 1
    
max_count = max(lengths.values())
print(n-max_count)
### BUGGY CODE ###

import collections

N = int(input())
a = list(map(int,input().split()))
Q = int(input())

c = collections.Counter(a)

for i in range(Q):
    arr = list(map(int,input().split()))
    B = arr[0]
    C = arr[1]

    if(C not in c):
        c[C] = 0

    c[C] += c[B]
    del c[B]

    sum = 0
    for key, cnt in c.items():
        sum += key*cnt

    print(sum)

### FIXED CODE ###

import collections

N = int(input())
a = list(map(int,input().split()))
su = sum(a)

Q = int(input())

c = collections.Counter(a)

for i in range(Q):
    arr = list(map(int,input().split()))
    B = arr[0]
    C = arr[1]

    if(C not in c):
        c[C] = 0

    num_B = c[B] # 配列に含まれるBの個数
    c[B] = 0
    c[C] += num_B
    # c[C] += c[B]
    # del c[B]

    # for key, cnt in c.items():
    #     sum -= items():
    #     sum += key*cnt

    su -= num_B * B # bのやつを減らす
    su += num_B * C # cのやつを増やすitems():

    print(su)
### BUGGY CODE ###

import fractions
from functools import reduce


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


def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

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

l = lcm(a)
answer = 0
for aa in a:
    answer += l // aa
    if answer >= 10 ** 9 + 7:
        answer = answer % (10 ** 9 + 7)

print(answer)


### FIXED CODE ###

# import math
# import fractions

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

mod = 10 ** 9 + 7


def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 not in a:
          a[2] = 0
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
              a[f] = 0
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
      if n not in a:
        a[n] = 0
      a[n] += 1
    return a


# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
# print(l)
# xs = {}
# xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  # print(ps)
  # xs[a[i]] = ps
  for k, v in ps.items():
    if k in l:
      l[k] = max(v, l[k])
    else:
      l[k] = v

# print(l)
# print(xs)

L = 1
for k, v in l.items():
  L = L * pow(k, v, mod) % mod

answer = 0
for x in a:
  answer = (answer + L * pow(x, mod - 2, mod)) % mod
print(answer)
### BUGGY CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
K = New_List[N-1]+1
Flag = [1]*K
for i in New_List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,K,i):
      Flag[j] = 0
    if New_List.count(i) > 1:
      res += -1
print(res)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if i != N-1 and List[i] == List[i+1]:
      res += -1
print(res)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())

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

two=[2**i for i in range(61)]
two=two[::-1]
log=[0]*61

for i in range(len(A)):
    for j in range(len(two)):
        if A[i]-two[j]>=0:
            A[i]-=two[j]
            log[j]+=1

ans=0
for i in range(len(two)):
    ans+=(N-log[i])*log[i]*two[i]

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


### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())

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

two=[2**i for i in range(61)]
two=two[::-1]
log=[0]*61

for i in range(len(A)):
    for j in range(len(two)):
        if A[i]-two[j]>=0:
            A[i]-=two[j]
            log[j]+=1

ans=0
for i in range(len(two)):
    ans+=(N-log[i])*log[i]*two[i]

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

S=list(input())
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  if S[i-1] is "A":
    A[i]=A[i-1]+1
    Q[i]=Q[i-1]
  elif S[i-1] is "?":
    A[i]=A[i-1]
    Q[i]=Q[i-1]+1
  else:
    A[i]=A[i-1]
    Q[i]=Q[i-1]
M=Q[N]
for i in range(1,N+1):
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
for i in range(1,N+1):
  if S[i-1] is "C":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2)))%(10**9+7))
  elif S[i-1] is "?":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3)))%(10**9+7))
  else:
    ABC[i]=ABC[i-1]
print(ABC[N]%(10**9+7))

### FIXED CODE ###

S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
  O=O%(10**9+7)
print(int(ABC[N]%(10**9+7)))
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
while stack:
    #print(stack)
    m,a,p=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(bisect_left(LRC,[p,0,0]),M):
            l,r,c=LRC[i]
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r,a+1])
            else:
                break
else:
    print(-1)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
x=0
while stack:
    #print(stack)
    m,a,p=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(x,M):
            l,r,c=LRC[i]
            x=i
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r,a+1])
            else:
                break
else:
    print(-1)
### BUGGY CODE ###

s=input()
t=''
skip=False
for i in range(len(s)-1):
    if skip:
        skip=False
        continue
    if s[i:i+2]=='BC':
        t+='D'
        skip=True
    else:
        t+=s[i]

ans,cnt=0,0
for i in range(len(t)):
    if t[i]=='A':
        cnt+=1
    if t[i] in ['B','C']:
        cnt=0
    if t[i]=='D':
        ans+=cnt
print(ans)


### FIXED CODE ###

s=input()
t=''
skip=False
for i in range(len(s)-1):
    if skip:
        skip=False
        continue
    if s[i:i+2]=='BC':
        t+='D'
        skip=True
    else:
        t+=s[i]

ans,cnt=0,0
for i in range(len(t)):
    if t[i]=='A':
        cnt+=1
    if t[i] in ['B','C']:
        cnt=0
    if t[i]=='D':
        ans+=cnt
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= []
dp3=[]
dp4=[]
for i in range(h):
    dp1.append([])
    dp2.append([])
    dp3.append([])
    dp4.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp2[i].append(-1)
        dp3[i].append(-1)
        dp4[i].append(-1)

for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]
a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)