Lennot

from heapq import *
from sys import stdin
sn,sm = stdin.readline().split(" ")
n=int(sn)
m=int(sm)
Lennot = [[] for i in range(n+1)]
for l in stdin.readlines():
	a,b,c = l.split()
	Lennot[int(a)].append( (int(b)*2,int(c)) )
n2 = n<<1
H = [-1]*(n2+2)
H[1] = 0
L = [(h,b+1) for b,h in Lennot[1]]
heapify(L)
np = n2
nv = n2+1
while True:
	h,b = heappop(L)
	if H[b] == -1:
		H[b] = h
		if b == np or b == nv: break
		par=b&1
		b>>=1
		if par:
			[heappush(L,(h,bn)) for bn,hn in Lennot[b] if H[bn] == -1]
		else:
			[heappush(L,(h+hn,bn+1)) for bn,hn in Lennot[b] if H[bn+1] == -1]
if H[nv] == -1:
	print(H[np])
elif H[np] == -1:
	print(H[nv])
else:
	print(min(H[nv],H[np]))

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED