import heapq def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 M = int(data[idx]) idx +=1 roads = [[] for _ in range(N+1)] for _ in range(M): a = int(data[idx]) idx +=1 b = int(data[idx]) idx +=1 c = int(data[idx]) idx +=1 roads[a].append( (b, c) ) roads[b].append( (a, c) ) T = list(map(int, data[idx:idx+N])) idx += N T = [0] + T # 1-based INF = 1 << 60 # dist[u][p] = minimal time to reach u with accumulated P=p dist = [dict() for _ in range(N+1)] initial_p = T[1] initial_time = initial_p dist[1][initial_p] = initial_time heap = [] heapq.heappush(heap, (initial_time, 1, initial_p)) answer = -1 while heap: t, u, p = heapq.heappop(heap) if u == N: answer = t break # Check if current t is larger than recorded minimal if p not in dist[u] or t > dist[u][p]: continue # Explore all adjacent roads for v, c in roads[u]: move_time = c // p new_time = t + move_time if v == N: # Check if this new_time is better for N if (p not in dist[v]) or new_time < dist[v].get(p, INF): dist[v][p] = new_time heapq.heappush(heap, (new_time, v, p)) else: new_p = p + T[v] new_time_v = new_time + T[v] if (new_p not in dist[v]) or new_time_v < dist[v].get(new_p, INF): dist[v][new_p] = new_time_v heapq.heappush(heap, (new_time_v, v, new_p)) print(answer) if __name__ == '__main__': main()