Lennot

from heapq import *

def main():
	n,m = [int(q) for q in raw_input().split(" ")]
	#n kaupungit, m lennot
	Lennot = {}
	for i in range(m):
		a,b,h = [int(q) for q in raw_input().split(" ")]
		if a not in Lennot:
			Lennot[a] = []
		Lennot[a].append( (b,h) )
	H = { (1,0) : 0 }
	L = []
	for b,h in Lennot[1]:
		heappush(L,(h,b,1))
	while len(L) != 0:
		h,b,par = heappop(L)		
		if par == 1:
			if (b,1) not in H:
				H[(b,1)] = h
				#FOR FREE
				if b in Lennot:
					for bn,hn in Lennot[b]:
						heappush(L,(h,bn,0) )
		if par == 0:
			if (b,0) not in H:
				H[(b,0)] = h
				#NOT FREE
				if b in Lennot:
					for bn,hn in Lennot[b]:
						heappush(L,(h+hn,bn,1) )
	if (n,0) not in H:
		print H[(n,1)]
	elif (n,1) not in H:
		print H[(n,0)]
	else:
		print min(H[(n,0)],H[(n,1)])
main()

Test 1

Subtask: 1

Verdict: ACCEPTED

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 1

Verdict: ACCEPTED

Test 4

Subtask: 1

Verdict: ACCEPTED

Test 5

Subtask: 1

Verdict: ACCEPTED

Test 6

Subtask: 2

Verdict: ACCEPTED

Test 7

Subtask: 2

Verdict: ACCEPTED

Test 8

Subtask: 2

Verdict: ACCEPTED

Test 9

Subtask: 2

Verdict: ACCEPTED

Test 10

Subtask: 2

Verdict: ACCEPTED

Test 11

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Subtask: 3

Verdict: ACCEPTED

Test 15

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Subtask: 3

Verdict: TIME LIMIT EXCEEDED