#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; typedef long long ll; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define repk(i, k, n) for (int i = k; i < (int)(n); i++) #define all(v) v.begin(), v.end() #define mod1 1000000007 #define mod2 998244353 #define mod3 100000007 #define vi vector #define vs vector #define vc vector #define vl vector #define vb vector #define vvi vector> #define vvc vector> #define vvl vector> #define vvb vector> #define vvvi vector>> #define vvvl vector>> #define pii pair #define pil pair #define pli pair #define pll pair #define vpii vector> #define vpll vector> #define vvpii vector>> #define vvpll vector>> // using mint = modint998244353; template void debug(T e) { cerr << e << endl; } template void debug(vector &v) { rep(i, v.size()) { cerr << v[i] << " "; } cerr << endl; } template void debug(vector> &v) { rep(i, v.size()) { rep(j, v[i].size()) { cerr << v[i][j] << " "; } cerr << endl; } } template void debug(vector> &v) { rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; } } template void debug(set &st) { for (auto itr = st.begin(); itr != st.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(multiset &ms) { for (auto itr = ms.begin(); itr != ms.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(map &mp) { for (auto itr = mp.begin(); itr != mp.end(); itr++) { cerr << itr->first << " " << itr->second << endl; } } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << H << " "; debug_out(T...); } using mint = modint998244353; int main() { ll N, M; cin >> N >> M; vector A(M); vector B(M); vector C(M); for (ll i = 0; i < M; i++) { cin >> A[i] >> B[i] >> C[i]; A[i]--; B[i]--; } vector T(N); for (ll i = 0; i < N; i++) { cin >> T[i]; } vector> graph(N, vector(0)); for (ll i = 0; i < M; i++) { graph[A[i]].push_back(make_pair(B[i], C[i])); graph[B[i]].push_back(make_pair(A[i], C[i])); } ll INF = 1000000000000000023; // これまでの塩むすびの合計が j のときの累計の最小値 // dp の遷移を DAG にしたいならすべき? vector> dp(N, vector(200002, INF)); priority_queue, vector>, greater>> pque; pque.push(make_pair(T[0], make_pair(0, T[0]))); dp[0][T[0]] = T[0]; while (pque.size()) { pair p = pque.top(); pque.pop(); ll now_cost = p.first; ll now_v = p.second.first; ll now_p = p.second.second; // debug_out(now_cost, now_v, now_p); if (dp[now_v][now_p] < now_cost) { continue; } if (now_v == N - 1) { cout << now_cost << endl; break; } for (ll i = 0; i < graph[now_v].size(); i++) { ll next_v = graph[now_v][i].first; ll next_e = graph[now_v][i].second; ll next_cost = now_cost + next_e / now_p + T[next_v]; if (dp[next_v][now_p + T[next_v]] > next_cost) { dp[next_v][now_p + T[next_v]] = next_cost; // debug_out(now_v, now_p, next_v, next_e, next_cost); pque.push( make_pair(next_cost, make_pair(next_v, now_p + T[next_v]))); } } } }