https://old.ynoip.cn/p/40060

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

const int maxn = 205;
const int inf = 0x3f3f3f3f;

typedef std::pair<int, int> PII;
int map[maxn][maxn];
int retime[maxn];
bool cp[maxn];
std::queue<int> ink;
int n, m, q;

void Floyd(int t);

int main(void) {
	memset(map, 0x3f, sizeof(map));
	std::cin >> n >> m;
	for (int i = 0; i < n; i++)
		std::cin >> retime[i];
	for (int i = 1, a, b, c; i <= m; i++) {
		std::cin >> a >> b >> c;
		map[a][b] = c;
		map[b][a] = c;
	}
	std::cin >> q;
	while (q--) {
		int x, y, t;
//		std::printf("--------------------\n");
		std::cin >> x >> y >> t;
		if (retime[y] > t || retime[x] > t) {
			std::printf("-1\n");
			continue;
		}
//		for (int i = 0; i < n; i++)
//			if (retime[i] <= t)
//				std::printf("%d ", i);
//		puts("");
		for (int i = 0; i < n; i++)
			if (!cp[i] && retime[i] <= t) {
				cp[i] = true;
				ink.push(i);
			}
		while (!ink.empty()) {
			Floyd(ink.front());
			ink.pop();
		}
		if (map[x][y] >= inf / 2)
			std::printf("-1\n");
		else
			std::printf("%d\n", map[x][y]);
//		std::printf("\n--------------------\n");
	}
	return 0;
}

void Floyd(int k) {
	for (int i = 0; i < n; i++)
		for (int u = 0; u < n; u++)
			map[i][u] = std::min(map[i][u], map[i][k] + map[k][u]);


	return;
}