#include <bits/stdc++.h>

using namespace std;

#define TRACE 1
#define tcout TRACE && cout

#define int long long
const int maxn = 1e5+10;
const int maxm = 2e5+10;
const int INF = (1<<31)-1; 
int head[maxm], vis[maxn]; 
long long dis[maxn]; 
int aaa[maxn];
int n, m, k, tot=0;
struct node 
{
	 int to, nxt, d;
}edge[maxm];
struct point{
	int dd,p;
	bool operator<(const point & x) const{
		return dd>x.dd;
	}
};
void add(int x, int y, int z) 
{
	 edge[tot].to = y;
	 edge[tot].d = z; 
	 edge[tot].nxt = head[x]; 
	 head[x] = tot++;
 }
void dijkstra()
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=INF;
	}
	dis[k]=0;
	memset(vis,0,sizeof(vis));
	priority_queue<point> q;
	point a;
	a.dd=0;
	a.p=k;
	q.push(a);
	while(!q.empty())
	{
		a=q.top();
		q.pop();
		int x=a.p;
		if(vis[x]) continue;
		vis[x]=1;  
		for(int i=head[x];i!=-1;i=edge[i].nxt)
		{
		
			int y=edge[i].to;
			
			if(dis[y] > dis[x] + edge[i].d +aaa[y]) 
			{  
				dis[y] = dis[x] +  edge[i].d +aaa[y];
				 a.dd = dis[y]; a.p = y;
				  q.push(a);
			 }
			
		}
		
	}
 
}
signed main()
{
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++)
	{
		cin>>aaa[i];
	}
    for(int i=1;i<=m;i++)
    {
    	int u,v,w;
    	cin>>u>>v>>w;
    	add(u,v,w);
	}
	k=1; 
	dijkstra();
	for(int i=2;i<=n;i++)
	{
		cout<<dis[i]+aaa[1]<<" ";
	}
	
	return 0;
}

这是上次ABC的D，求调