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

vector <int> dy = {0, 1, 0, -1};
vector <int> dx = {1, 0, -1, 0};

const int INF = 1000000000;
const ll INFLL = 100000000000000000;

int main(){
    int n, m; cin >> n >> m;
    vector <ll> a(n);
    rep(i, n) cin >> a.at(i);
    vector <vector<int>> G(n);
    rep(i, m){
        int x, y; cin >> x >> y;
        x--; y--;
        G.at(x).push_back(y);
    }

    vector <ll> dp(n, -INFLL);
    ll ans = -INFLL;
    vector <int> seen(n, -1);
    for(int i = n - 1; i >= 0; i --){
        seen.at(i) = 1;
        auto children = G.at(i);
        //if(children.size() == 0) continue;
        //sort(children.rbegin(), children.rend());
        // auto great_child = children.at(0);
        // dp.at(i) = max(dp.at(i), max(dp.at(great_child) + a.at(great_child) - a.at(i), a.at(great_child) - a.at(i)));
        for(auto child: children){
            dp.at(i) = max(dp.at(i), max(dp.at(child) + a.at(child) - a.at(i), a.at(child) - a.at(i)));
        }
        ans = max(ans, dp.at(i));
        //cout << dp.at(i) << endl;
    }

    cout << ans << endl;

}
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 2050,inf = 1e9;
int n,m,x,y,z,last[maxn],ms[maxn],vis[maxn],dis[maxn],g[maxn][maxn];
struct Edge{
	int v,w,nxt;
}e[maxn];
priority_queue <pair<int,int> > q;
int read(){
	int x = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + (c ^ 48),c = getchar();
	return x;
}
inline void insert(int u,int v,int w){
	static int cnt = 0;
	e[++cnt] = {v,w,last[u]},last[u] = cnt;
}
void Dijkstra(int S){
	for(int i = 1; i <= n; i ++) vis[i] = 0,dis[i] = inf;
	dis[S] = 0,q.push({0,S});
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = last[u]; i; i = e[i].nxt){
			int v = e[i].v;
			if(dis[u] + e[i].w < dis[v]){
				dis[v] = dis[u] + e[i].w;
				q.push({-dis[v],v});
			}
		}
	}
	for(int i = 1; i <= n; i ++) g[S][i] = dis[i];
	g[S][S] = inf;
}
int main(){
	n = read(),m =  read();
	for(int i = 1; i <= n; i ++) ms[i] = inf;
	for(int i = 1; i <= m; i ++){
		x = read(),y = read(),z = read();
		if(x == y){
			ms[x] = min(ms[x],z);
			continue;
		}
		insert(x,y,z);
	}
	for(int i = 1; i <= n; i ++) Dijkstra(i);
	for(int i = 1; i <= n; i ++){
		int mn = inf;
		for(int j = 1; j <= n; j ++) mn = min(mn,g[i][j] + g[j][i]);
		printf("%d\n",mn == inf && ms[i] == inf ? -1 : min(mn,ms[i]));
	}
	return 0;
}