时间复杂度应该是对的，但是一直tle

#include <bits/stdc++.h>
using namespace std;
int T = 0;
int n = 0;
int m = 0;
int q = 0;

struct qwq{
	int u;
	int v;
	int w;
}e[300010];
inline bool cmp(qwq a, qwq b){
	return a.w < b.w;
}
int dp[410][410][410];
int sb[410];
inline int read(){
     char ch=getchar();int x=0,f=1;
     while(ch<'0' || ch>'9')    {if(ch=='-')f=-1;ch=getchar();}
     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
     return x*f;
}
int a = 0;
int b = 0;
int kk = 0;
int l = 0;
int r = 0;
signed main(){
	ios::sync_with_stdio(0);
//	cin.tie(0);
	cout.tie(0);
	T = read();
//	cin >> T; 
	while(T --){
		n = read();
		m = read();
		q = read();
//		cin >> n >> m >> q;
		for(register int i = 1; i <= n; i++){
			for(register int j = 1; j <= n; j++){
				if(i != j)dp[i][j][0] = 1e9;
			}
		}
		for(register int i = 1; i <= m; i++){
//			cin >> e[i].u >> e[i].v >> e[i].w;
			e[i].u = read();
			e[i].v = read();
			e[i].w = read();
			dp[e[i].u][e[i].v][0] = 1;
			dp[e[i].v][e[i].u][0] = 1;
		}
		sort(e + 1, e + 1 + m, cmp);
		for(register int k = 1; k <= n; k++){
			for(register int i = 1; i <= n; i++){
				for(register int j = 1; j <= n; j++){
					dp[i][j][0] = min(dp[i][j][0], dp[i][k][0] + dp[k][j][0]);
				}
			}
		}
		register int cnt = 0;
		for(register int op = 1; op <= m; op++){
			int u = e[op].u;
			int v = e[op].v;
			if(!dp[u][v][cnt]){
				continue;
			}
			sb[++ cnt] = e[op].w;
			for(register int i = 1; i <= n; i++){
				for(register int j = 1; j <= n; j++){
					dp[i][j][cnt] = dp[i][j][cnt - 1];
				}
			}
			dp[e[op].u][e[op].v][cnt] = 0;
//			dp[e[op].v][e[op].u][cnt] = 0;
			for(register int i = 1; i <= n; i++){
				for(register int j = 1; j <= n; j++){
					
					dp[i][j][cnt] = min(dp[i][j][cnt], dp[i][e[op].u][cnt] + dp[e[op].v][j][cnt]);
					dp[i][j][cnt] = min(dp[i][j][cnt], dp[i][e[op].v][cnt] + dp[e[op].u][j][cnt]);
				}
			}
		}
		while(q --){
			a = read();
			b = read();
			kk = read();
//			cin >> a >>b >> kk;
			
			l = 1;
			r = cnt;
			while(l <= r){
				register int  mid = (l + r) >> 1;
				if(dp[a][b][mid] <= kk - 1){
					r = mid - 1;
				}
				else{
					l = mid + 1;
				}
			}
			cout << sb[l] << ' ';
//			printf("%d ", sb[l]);
		}
		
//		printf("\n");
	}
}