#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
	#define out(x)
#else
	#define out(x) cerr<<#x"="<<(x)<<endl
#endif
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define MAXM 3001
struct Edge{
	int u, v, w, next;
	void get(){
		scanf("%d%d%d",&u,&v,&w);
		--u; --v;
	}
	bool operator<(Edge r)const{return w<r.w;}
} e[MAXM];
vi E[151], des[151];
vi ee[MAXM];
struct query{
	int a, b, c, t;
	void get(int _t){
		scanf("%d%d%d",&a,&b,&c);
		--a; --b;
		t=_t;
	}
	bool operator<(query r)const{
		return c<r.c;
	}
};
vector<query> qu[151];
int ans[1123];
inline bool takemin(int &x, int y){
	if(y==-1)return 0;
	if(x==-1 || y<x){
		x=y;
		return 1;
	}
	return 0;
}
int n, m;
int d[MAXM];
int dd[151];
bool vis[2][MAXM];
vi q[2];
void spfa(int x, vector<query> &qu){
	REP(i,2)memset(vis[i], 0, m);
	memset(dd, -1, sizeof dd);
	q[0].clear(); q[1].clear();
	REP(i,m)d[i]=-1;
	dd[x]=0;
	REP(i,E[x].size()){
		int j=E[x][i], w=e[j].w;
		while(~j && takemin(d[j], w)){
			takemin(dd[e[j].v], w);
			if(!vis[0][j]){
				q[0].pb(j);
				vis[0][j]=1;
			}
			j=e[j].next;
		}
	}
	int u=0, c=1, z=0;
	while(q[u].size()){
		while(z<qu.size() && qu[z].c==c){
			int b=qu[z].b, id=qu[z].t;
			takemin(ans[id], dd[b]);
			++z;
		}
		if(z==qu.size())break;
		int v=u^1;
		vi &q0=q[u], &q1=q[v];
		bool (&v0)[MAXM]=vis[u], (&v1)[MAXM]=vis[v];
		q1.clear();
		sort(q0.begin(), q0.end());
		reverse(q0.begin(), q0.end());
		REP(i,q0.size()){
			int j=q0[i]; //edge j
			v0[j]=0;
			int u=e[j].v;
			REP(k,ee[j].size()){
				int id=ee[j][k];
				int dis=d[j]+e[id].w;
				while(~id && takemin(d[id],dis)){
					takemin(dd[e[id].v], dis);
					if(!v1[id]){
						q1.pb(id);
						v1[id]=1;
					}
					id=e[id].next;
				}
			}
		}
		u=v;
		++c;
	}
	while(z<qu.size()){
		int b=qu[z].b, id=qu[z].t;
		takemin(ans[id], dd[b]);
		++z;
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int q;
		scanf("%d%d%d",&n,&m,&q);
		REP(i,n){
			E[i].clear();
			des[i].clear();
			qu[i].clear();
		}
		REP(i,m){
			e[i].get();
			ee[i].clear();
		}
		sort(e, e+m);
		REP(i,m){
			int v=e[i].v;
			if(des[v].size())
				e[des[v].back()].next=i;
			des[v].pb(i);
			e[i].next=-1;
			E[e[i].u].pb(i);
		}
		REP(x,n)if(des[x].size()){
			int j=0;
			REP(i,E[x].size()){
				while(j+1<des[x].size() && des[x][j+1]<E[x][i])++j;
				if(des[x][j]<E[x][i])ee[des[x][j]].pb(E[x][i]);
			}
		}
		REP(i,q){
			ans[i]=-1;
			query tmp;
			tmp.get(i);
			tmp.c=min(tmp.c, n);
			if(tmp.c)qu[tmp.a].pb(tmp);
		}
		REP(i,n)sort(qu[i].begin(), qu[i].end());
		REP(i,n)if(qu[i].size()){
			spfa(i, qu[i]);
		}
		REP(i,q)printf("%d\n", ans[i]);
	}
}