#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
const int INF=1e9+7;
int m,n,c;
struct edge{
    int to,val;
};
vector<edge>G[N];
int dis[N],vis[N];
void spfa(int x){
    queue<int>q;
    for(int i=1;i<=n;i++){
        vis[i]=0;
        dis[i]=INF;
    }
    dis[x]=0;
    vis[x]=1;
    q.push(x);
    while(!q.empty()){
        int  u=q.front();
        q.pop();
        vis[u]=0;
        for(auto to:G[u]){
            int v=to.to,w=to.val;
			if(dis[v]>=dis[u]+w){
				dis[v]=dis[u]+w;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
			}
        }
    }
}
int main(){
	freopen("usaco_Feb_timeline.in","r",stdin);
	freopen("usaco_Feb_timeline.out","w",stdout);
    cin>>n>>m>>c;
    int s;
    for(int i=1;i<=n;i++){
        cin>>s;
        G[0].push_back({i,-s});
    }
    int x,y,z;
    for(int i=1;i<=c;i++){
        cin>>x>>y>>z;
        G[x].push_back({y,-z});
    }
    spfa(0);
    for(int i=1;i<=n;i++){
        cout<<-dis[i]<<"\n";
    }

	return 0;
}