#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for(int i = (int)a, _b = (int)b; i < _b; ++ i)
#define PER(i, a, b) for(int i = (int)a, _b = (int)b; i > _b; -- i)
#define TRcon(a, it) for(auto it = (a).begin(); it != (a).end(); ++ it)
#define pb push_back
#define mp make_pair
#define all(a) (a.begin(), a.end())
#define sz(a) ((int) a.size())
#define ms(a, val) memset(a, val, sizeof (a))
#define INF 1000000000
#define inp(a) scanf("%d", &a)
#define inpp(a, b) scanf("%d %d", &a, &b)
#define inppp(a, b, c) scanf("%d %d %d", &a, &b, &c)
#define readfrom(a) freopen(a, "r", stdin)
#define writeto(a) freopen(a, "w", stdout)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<string, string> ss;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef set <int> si;
typedef map<int, int> mii;
typedef map<ii, int> mpi;
typedef map<string, int> msi;
const int N = 151;
vii G[N];
bool vis[N];
int V, E, Q;
struct m {
int a, b, c, d;
m() {}
m(int _a, int _b, int _c, int _d) {
a = _a, b = _b, c = _c, d = _d;
}
bool operator< (const m &o) const {
return a < o.a;
}
};
map <m, int> mem;
int DFS(int u, int pd, int dist, int C, int des) {
if (C == 0) {
if (u == des)
return dist;
return INF;
}
//cout << u + 1 << endl;
if (u == des)
return dist;
int ans = INF;
TRcon(G[u], v) {
if (!vis[v->first]) {
if (v->second >= pd) {
vis[v->first] = true;
ans = min(ans, DFS(v->first, v->second, dist + v->second, C - 1, des));
vis[v->first] = false;
}
}
}
return ans;
}
map <iii, int> yrab;
int main(void) {
//readfrom("in.txt");
//writeto("out.txt");
int TC; inp(TC);
while (TC--) {
inppp(V, E, Q);
REP(i, 0, V + 1) {
G[i].clear();
}
REP(i, 0, E) {
int u, v, w; inppp(u, v, w);
G[u - 1].push_back(ii(v - 1, w));
}
REP(i, 0, Q) {
int A, B, C; inppp(A, B, C);
int ans = DFS(A - 1, 0, 0, C, B - 1);
printf(ans == INF ? "-1\n" : "%d\n", ans);
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIFJFUChpLCBhLCBiKQkJCQkJZm9yKGludCBpID0gKGludClhLCBfYiA9IChpbnQpYjsgaSA8IF9iOyArKyBpKQojZGVmaW5lIFBFUihpLCBhLCBiKQkJCQkJZm9yKGludCBpID0gKGludClhLCBfYiA9IChpbnQpYjsgaSA+IF9iOyAtLSBpKQojZGVmaW5lIFRSY29uKGEsIGl0KQkJCQkJZm9yKGF1dG8gaXQgPSAoYSkuYmVnaW4oKTsgaXQgIT0gKGEpLmVuZCgpOyArKyBpdCkKI2RlZmluZSBwYgkJCQkJCQkJCQlwdXNoX2JhY2sKI2RlZmluZSBtcAkJCQkJCQkJCQltYWtlX3BhaXIKI2RlZmluZSBhbGwoYSkJCQkJCQkJCShhLmJlZ2luKCksIGEuZW5kKCkpCiNkZWZpbmUgc3ooYSkJCQkJCQkJCQkoKGludCkgYS5zaXplKCkpCiNkZWZpbmUgbXMoYSwgdmFsKQkJCQkJCW1lbXNldChhLCB2YWwsIHNpemVvZiAoYSkpCiNkZWZpbmUgSU5GCQkJCQkJCQkJCTEwMDAwMDAwMDAKI2RlZmluZSBpbnAoYSkJCQkJCQkJCXNjYW5mKCIlZCIsICZhKQojZGVmaW5lIGlucHAoYSwgYikJCQkJCQlzY2FuZigiJWQgJWQiLCAmYSwgJmIpIAojZGVmaW5lIGlucHBwKGEsIGIsIGMpCQkJCXNjYW5mKCIlZCAlZCAlZCIsICZhLCAmYiwgJmMpCiNkZWZpbmUgcmVhZGZyb20oYSkJCQkJCQlmcmVvcGVuKGEsICJyIiwgc3RkaW4pCiNkZWZpbmUgd3JpdGV0byhhKQkJCQkJCWZyZW9wZW4oYSwgInciLCBzdGRvdXQpCgoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBpaTsKdHlwZWRlZiBwYWlyPGludCwgaWk+ICBpaWk7CnR5cGVkZWYgcGFpcjxzdHJpbmcsIHN0cmluZz4gc3M7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPGJvb2w+IHZiOwp0eXBlZGVmIHZlY3RvcjxpaT4gdmlpOwp0eXBlZGVmIHZlY3RvcjxzdHJpbmc+IHZzOwp0eXBlZGVmIHNldCA8aW50PiBzaTsKdHlwZWRlZiBtYXA8aW50LCBpbnQ+IG1paTsKdHlwZWRlZiBtYXA8aWksIGludD4gbXBpOwp0eXBlZGVmIG1hcDxzdHJpbmcsIGludD4gbXNpOwoKY29uc3QgaW50IE4gPSAxNTE7Cgp2aWkgR1tOXTsKYm9vbCB2aXNbTl07CmludCBWLCBFLCBROwoKc3RydWN0IG0gewoJaW50IGEsIGIsIGMsIGQ7CgltKCkge30KCW0oaW50IF9hLCBpbnQgX2IsIGludCBfYywgaW50IF9kKSB7CgkJYSA9IF9hLCBiID0gX2IsIGMgPSBfYywgZCA9IF9kOwoJfQoJYm9vbCBvcGVyYXRvcjwgKGNvbnN0IG0gJm8pIGNvbnN0IHsKCQlyZXR1cm4gYSA8IG8uYTsKCX0KfTsKCm1hcCA8bSwgaW50PiBtZW07CgppbnQgREZTKGludCB1LCBpbnQgcGQsIGludCBkaXN0LCBpbnQgQywgaW50IGRlcykgewoJaWYgKEMgPT0gMCkgewoJCWlmICh1ID09IGRlcykKCQkJcmV0dXJuIGRpc3Q7CgkJcmV0dXJuIElORjsKCX0KCS8vY291dCA8PCB1ICsgMSA8PCBlbmRsOwoJaWYgKHUgPT0gZGVzKQoJCXJldHVybiBkaXN0OwoJaW50IGFucyA9IElORjsKCVRSY29uKEdbdV0sIHYpIHsKCQlpZiAoIXZpc1t2LT5maXJzdF0pIHsKCQkJaWYgKHYtPnNlY29uZCA+PSBwZCkgewoJCQkJdmlzW3YtPmZpcnN0XSA9IHRydWU7CgkJCQlhbnMgPSBtaW4oYW5zLCBERlModi0+Zmlyc3QsIHYtPnNlY29uZCwgZGlzdCArIHYtPnNlY29uZCwgQyAtIDEsIGRlcykpOwoJCQkJdmlzW3YtPmZpcnN0XSA9IGZhbHNlOwoJCQl9CgkJfQoJfQoJcmV0dXJuIGFuczsKfQoKbWFwIDxpaWksIGludD4geXJhYjsKCmludCBtYWluKHZvaWQpIHsKCS8vcmVhZGZyb20oImluLnR4dCIpOwoJLy93cml0ZXRvKCJvdXQudHh0Iik7CglpbnQgVEM7IGlucChUQyk7Cgl3aGlsZSAoVEMtLSkgewoJCWlucHBwKFYsIEUsIFEpOwoJCVJFUChpLCAwLCBWICsgMSkgewoJCQlHW2ldLmNsZWFyKCk7CgkJfQoJCVJFUChpLCAwLCBFKSB7CgkJCWludCB1LCB2LCB3OyBpbnBwcCh1LCB2LCB3KTsKCQkJR1t1IC0gMV0ucHVzaF9iYWNrKGlpKHYgLSAxLCB3KSk7CgkJfQoJCVJFUChpLCAwLCBRKSB7CgkJCWludCBBLCBCLCBDOyBpbnBwcChBLCBCLCBDKTsKCQkJaW50IGFucyA9IERGUyhBIC0gMSwgMCwgMCwgQywgQiAtIDEpOwoJCQlwcmludGYoYW5zID09IElORiA/ICItMVxuIiA6ICIlZFxuIiwgYW5zKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQo=