park.cpp

#include <map>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <iostream>
#include <algorithm>
#include <climits>

std::vector<std::vector<std::pair<double, double>>> adj;
std::vector<long long> d, c;

void dijktras(long long s)
{
	d[s] = 0;
	std::priority_queue<std::pair<double, double>, std::vector<std::pair<double, double>>, std::greater<std::pair<double, double>>> pq;
	pq.push({0, s});
	while (!pq.empty())
	{
		long long v = pq.top().second;
		long long d_v = pq.top().first;
		pq.pop();
		if (d[v] != d_v)
			continue;
		for (auto &edge : adj[v])
		{
			long long len = edge.second;
			long long to = edge.first;

			if (d[to] > d[v] + len)
			{
				d[to] = d[v] + len;
				pq.push({d[to], to});
			}
		}
	}
}

int main()
{

	long long n, m, f;
	std::cin >> n >> m >> f;
	adj.resize(n + 1);
	d.assign(n + 1, LONG_LONG_MAX);
	c.resize(n + 1);
	for (size_t i = 1; i <= n; i++)
		std::cin >> c[i];

	while (m--)
	{
		long long u, v, w;
		std::cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	long long k;
	std::cin >> k;



	dijktras(1);
	std::multiset<long long> ml;
	std::vector<std::pair<long long, long long>> v;
	for (size_t i = 1; i <= n; i++)
		v.push_back({d[i], i});
	std::sort(v.begin(), v.end());

	for (size_t i = 0; i < v.size(); i++){

		int u = v[i].second;
		for (int j = 0; j < c[u]; j++)
		{
			ml.insert(v[i].first);
			if (ml.size() == k)
				break;
		}
		if (ml.size() == k)
			break;
	}
	for (auto &u : ml)
		std::cout << u + f << " ";
	if (k > ml.size())
		for (size_t i = 0; i < k - ml.size(); i++)
			std::cout << -1 << " ";

	return EXIT_SUCCESS;
}