N=1e10

def find_min(x,ran):
    res=0
    mm=N
    for i in ran:
        if x[i]<mm:
            mm=x[i]
            res=i
    return res

n,m=map(int,input().split(" "))
dist=[None]*n
for i in range(n):
    dist[i]=[-1]*n
for i in range(m):
    u,v,c=map(int,input().split(" "))
    dist[u-1][v-1]=c
    dist[v-1][u-1]=c

res=[N]*n
res[0]=0
spot=list(range(n))
for i in range(n):
    m=find_min(res,spot)
    spot.remove(m)
    for j in spot:
        if dist[m][j]>=0:
            res[j]=min(res[j],res[m]+dist[m][j])

print(res[n-1])