#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e4 + 5;

long long dist[mxN][35];
vector<pair<int, int>> g[mxN];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, t;
	cin >> n >> m >> t;
	vector<int> c(n);
	for(int i = 0; i < n; i++) cin >> c[i];
	for(int i = 0; i < m; i++){
		int a, b, d;
		cin >> a >> b >> d;
		a--, b--;
		g[a].push_back({b, d});
		g[b].push_back({a, d});
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= t; j++)
			dist[i][j] = 1e18;
	dist[0][t] = 0LL;
	set<pair<long long, pair<int, int>>> q;
	q.insert(make_pair(0LL, make_pair(0, t)));
	while(!q.empty()){
		pair<long long, pair<int, int>> cur = *q.begin();
		q.erase(q.begin());
		for(int i = cur.second.second; i <= (!c[cur.second.first] ? cur.second.second : t); i++){
			long long cst = cur.first + (c[cur.second.first] * (i - cur.second.second));
			for(pair<int, int> x : g[cur.second.first]){
				if(i >= x.second){
					if(cst < dist[x.first][i - x.second]){
						q.erase(make_pair(dist[x.first][i - x.second], make_pair(x.first, i - x.second)));
						dist[x.first][i - x.second] = cst;
						q.insert(make_pair(dist[x.first][i - x.second], make_pair(x.first, i - x.second)));
					}
				}
			}
		}
	}
	for(int i = 1; i < n; i++){
		long long mn = 1e18;
		for(int j = 0; j <= t; j++) mn = min(mn, dist[i][j]);
		if(mn == 1e18) mn = -1;
		cout << mn;
		if(i == (n - 1)) cout << '\n';
		else cout << ' ';
	}
	return 0;
}