import sys input = sys.stdin.readline from heapq import heappop,heappush N,M=map(int,input().split()) E=[[] for i in range(N)] for i in range(M): a,b,c=map(int,input().split()) a-=1 b-=1 E[a].append((b,c)) E[b].append((a,c)) T=list(map(int,input().split())) DP=[[1<<60]*N for i in range(1050)] DP[0][0]=0 Q=[(0,0,0)] while Q: dis,eat,town=heappop(Q) if DP[eat][town]!=dis: continue eat=min(1049,eat+T[town]) for to,cost in E[town]: if DP[eat][to]>dis+cost//eat+T[town]: DP[eat][to]=dis+cost//eat+T[town] heappush(Q,(DP[eat][to],eat,to)) ANS=1<<60 for i in range(1050): ANS=min(ANS,DP[i][N-1]) print(ANS)