Lennot

'''
Created on 9.10.2015

@author: siiri
'''
from queue import PriorityQueue
inf=999999999

n,m=map(int,input().split())
yht=[]
for i in range(m):
    yht.append(list(map(int, input().split())))
    
a=[]
b=[]
c=[]
for i in range(n+1):
    a.append([])
    b.append(1000000005)
    c.append(False)

for mist,minn,h in yht:
    a[mist].append([h, minn])  
    
keko=PriorityQueue()
keko.put((0,1))

while not keko.empty():
    hinta1, kaupunki=keko.get()
    if c[kaupunki]: continue
    c[kaupunki]=True
    for hinta2,minne in a[kaupunki]:
        hintasumma=hinta1+hinta2
        if not a[minne] and hintasumma<b[minne]:
                b[minne]=hintasumma
        for hint,minne2 in a[minne]:
            if hintasumma<b[minne2]:
                b[minne]=hintasumma
                b[minne2] = hintasumma
                keko.put((hintasumma, minne2))
            
            

print(b[n])
            
            

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED