#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, e) for (int i = (int)(s); i < (int)(e); ++i)

template<typename T>
bool chmin(T &a, T b) {
	return ((a > b) ? (a = b, true) : (false));
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	
	int N, M;
	cin >> N >> M;
	vector<vector<pair<int, int>>> G(N);
	rep(i, 0, M) {
		int A, B, C;
		cin >> A >> B >> C;
		--A, --B;
		G[A].push_back({B, C});
		G[B].push_back({A, C});
	}
	vector<int> T(N);
	rep(i, 0, N) cin >> T[i];
	
	const ll INF = 1ll << 60;
	
	int maxiC = 1010;
	vector dist(N, vector<ll>(maxiC + 1, INF));
	priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> que;
	dist[0][T[0]] = T[0];
	que.push({T[0], {0, T[0]}});
	
	while (!que.empty()) {
		ll d = que.top().first;
		int v = que.top().second.first;
		int p = que.top().second.second;
		que.pop();
		
		if (d > dist[v][p]) continue;
		
		for (pair<int, int> e : G[v]) {
			if (chmin(dist[e.first][min(maxiC, p + T[e.first])], dist[v][p] + e.second / p + T[e.first])) {
				que.push({dist[e.first][min(maxiC, p + T[e.first])], {e.first, min(maxiC, p + T[e.first])}});
			}
		}
	}
	
	ll ans = INF;
	rep(i, 0, maxiC + 1) ans = min(ans, dist[N - 1][i]);
	cout << ans << '\n';
}