#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> const int nx = 1e6+5; const int INF = 1e9; int n, m, coin[nx]; vector<pii> adj[nx]; priority_queue<pii, vector<pii>, greater<pii>> pq; int solve(int src) { vector<int> dist(nx, INF), vs(nx, 0); dist[src] = 0; pq.push({0, src}); while(!pq.empty()) { auto [cw, u] = pq.top(); pq.pop(); if(vs[u] || cw > dist[u]) continue; vs[u] = 1; // cout << "src : " << src << " cw : " << cw << " u : " << u << '\n'; for(auto [v, nw] : adj[u]) { if(dist[v] > dist[u] + nw) { dist[v] = dist[u] + nw; pq.push({dist[v], v}); } } } int mx = coin[src]; for(int i=1;i<=n;i++) mx = max(mx, coin[i] - dist[i]); return mx; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> m; for(int i=1;i<=n;i++) cin >> coin[i]; for(int i=1;i<=m;i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } for(int i=1;i<=n;i++) cout << solve(i) << '\n'; return 0; }