C++ 解法, 执行用时: 494ms, 内存消耗: 15644K, 提交时间: 2021-11-05 18:54:38

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read() {
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}

const int N = 45;
const int mod = 1e9 + 7;

int n, m, Q;
int a[N][N];
int f[31][31][N][N][2];

void mul(int f[N][N][2], int a[N][N][2]) {
	static int c[N][N][2]; memset(c, 0, sizeof(c));

	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			for (int k = 1; k <= n; k ++) {
				c[i][j][0] = (c[i][j][0] + 1ll * a[i][k][0] * a[k][j][0]) % mod;
				c[i][j][0] = (c[i][j][0] + 1ll * a[i][k][1] * a[k][j][1]) % mod;
				c[i][j][1] = (c[i][j][1] + 1ll * a[i][k][0] * a[k][j][1]) % mod;
				c[i][j][1] = (c[i][j][1] + 1ll * a[i][k][1] * a[k][j][0]) % mod;
			}

	memcpy(f, c, sizeof(c));
}

void mulstar(int a[N][2], int b[N][N][2]) {
	static int c[N][2]; memset(c, 0, sizeof(c));

	for (int j = 1; j <= n; j ++)
		for (int k = 1; k <= n; k ++) {
			c[j][0] = (c[j][0] + 1ll * a[k][0] * b[k][j][0]) % mod;
			c[j][0] = (c[j][0] + 1ll * a[k][1] * b[k][j][1]) % mod;
			c[j][1] = (c[j][1] + 1ll * a[k][0] * b[k][j][1]) % mod;
			c[j][1] = (c[j][1] + 1ll * a[k][1] * b[k][j][0]) % mod;
		}

	memcpy(a, c, sizeof(c));
}

void calc(int index) {
	for (int u = 1; u <= n; u ++)
		for (int v = 1; v <= n; v ++) {
			if (a[u][v] == 0x3f3f3f3f) continue;
			int w = a[u][v] >> index & 1;
			f[index][0][u][v][w] = 1;
		}

	for (int i = 1; i <= 30; i ++)
		mul(f[index][i], f[index][i - 1]);
}

void work() {
	int S = read(), T = read(), k = read() - 1;
	int ans = 0;

	for (int index = 0; index <= 30; index ++) {
		int d[N][2]; memset(d, 0, sizeof(d));
		for (int i = 1; i <= n; i ++) {
			if (a[S][i] == 0x3f3f3f3f) continue;
			int w = a[S][i] >> index & 1;
			d[i][w] = 1; 
		}

		for (int i = 0; i <= 30; i ++)
			if (k >> i & 1) mulstar(d, f[index][i]);

		ans = (ans + 1ll * (1 << index) * d[T][1]) % mod;
	}

	printf("%d\n", ans);
}

int main() {
	n = read(), m = read();

	memset(a, 0x3f, sizeof(a));
	for (int i = 1; i <= m; i ++) {
		int u = read(), v = read(), w = read();
		a[u][v] = a[v][u] = w;
	}

	for (int index = 0; index <= 30; index ++)
		calc(index);

	Q = read();

	while (Q --)    work();

	return 0;
}