x

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, t, c[85], dp[85][85], w[85][85][85], nxt[85][85];
vector <int> to[85];
// dp[i][j] 表示在第 i 天到达第 j 个城市的最小花费 

void init() {
	memset(dp, 0x3f, sizeof(dp));
	dp[0][1] = 0;
	memset(nxt, 0, sizeof(nxt));
	for (int i = 1; i <= n; i ++) to[i].clear();
	return ;
}
void solve() {
	cin >> n >> m >> t;
	init();
	for (int i = 1, x, y; i <= m; i ++) {
		cin >> x >> y;
		for (int j = 1; j <= t; j ++) cin >> w[x][y][j];
		for (int j = 1; j <= t; j ++) w[y][x][j] = w[x][y][j];
		to[x].emplace_back(y), to[y].emplace_back(x);
	}
	for (int i = 1; i <= n; i ++) cin >> c[i];
	for (int i = 1; i <= t; i ++) {
		for (int j = 1; j <= n; j ++) {
			for (int k : to[j]) {
				if (nxt[i - 1][k] != j) {
					if (dp[i][j] > dp[i - 1][k] + w[k][j][i]) dp[i][j] = dp[i - 1][k] + w[k][j][i], nxt[i][j] = k;
					else if (dp[i][j] == dp[i - 1][k] + w[k][j][i]) nxt[i][j] = -1;
				} else {
					if (dp[i][j] > dp[i - 1][k] + w[k][j][i] + c[k]) dp[i][j] = dp[i - 1][k] + w[k][j][i] + c[k], nxt[i][j] = k;
					else if (dp[i][j] == dp[i - 1][k] + w[k][j][i] + c[k]) nxt[i][j] = -1;
				}
			}
		}
	}
	int ans = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1; i <= n; i ++) ans = min(ans, dp[t][i]);
	cout << ans << '\n';
	return ;
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("aviation.in", "r", stdin);
//	freopen("aviation.out", "w", stdout);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}