#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 128;
template < class T, T INF >
struct dijkstra_kth_shortest_path {
struct edge {
int to;
T w;
edge(){}
edge(int a, T b) {
to=a;
w=b;
}
};
struct el {
int vertex;
T cost;
el(){}
el(int a, T b) {
vertex=a;
cost=b;
}
bool operator <(const el &a) const {
return cost>a.cost;
}
};
int n;
vector < vector < edge > > v;
void initialize(int k) {
n=k;
v.assign(n+1,vector < edge > ());
}
void add_edge(int from, int to, T w) {
v[from].push_back(edge(to,w));
}
void run(int start, vector < T > *dist, int k) {
int i,to;
T current_distance,w;
el curr;
priority_queue < el > q;
for(i=1;i<=n;i++) dist[i].clear();
q.push(el(start,0));
while(!q.empty()) {
curr=q.top();
q.pop();
if((int)(dist[curr.vertex].size())>=k) continue;
if(curr.cost>0) dist[curr.vertex].push_back(curr.cost);
for(i=0;i<(int)(v[curr.vertex].size());i++) {
to=v[curr.vertex][i].to;
if((int)(dist[to].size())>=k) continue;
w=v[curr.vertex][i].w;
current_distance=w+curr.cost;
q.push(el(to,current_distance));
}
}
}
};
int tests,current_case;
int n,m;
dijkstra_kth_shortest_path < int, 1000000007 > d;
vector < int > dist[N][N];
int q;
void message(int current_case) {
//cerr<<"Case "<<current_case<<" solved!"<<endl;
fprintf(stderr, "Case %d solved!\n", current_case);
}
int main() {
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int i,x,y,z;
tests=1;
//scanf("%d", &tests);
//cin>>tests;
for(current_case=1;current_case<=tests;current_case++) {
scanf("%d %d", &n, &m);
d.initialize(n);
for(i=1;i<=m;i++) {
scanf("%d %d %d", &x, &y, &z);
d.add_edge(x,y,z);
}
for(i=1;i<=n;i++) {
d.run(i,dist[i],100);
}
scanf("%d", &q);
while(q--) {
scanf("%d %d %d", &x, &y, &z);
if((int)(dist[x][y].size())<z) {
printf("-1\n");
}
else {
printf("%d\n", dist[x][y][z-1]);
}
}
MESSAGE:
message(current_case);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZW5kbCAnXG4nCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE4gID0gMTI4OwoKdGVtcGxhdGUgPCBjbGFzcyBULCBUIElORiA+CnN0cnVjdCBkaWprc3RyYV9rdGhfc2hvcnRlc3RfcGF0aCB7CiAgICBzdHJ1Y3QgZWRnZSB7CiAgICAgICAgaW50IHRvOwogICAgICAgIFQgdzsKICAgICAgICBlZGdlKCl7fQogICAgICAgIGVkZ2UoaW50IGEsIFQgYikgewogICAgICAgICAgICB0bz1hOwogICAgICAgICAgICB3PWI7CiAgICAgICAgfQogICAgfTsKICAgIHN0cnVjdCBlbCB7CiAgICAgICAgaW50IHZlcnRleDsKICAgICAgICBUIGNvc3Q7CiAgICAgICAgZWwoKXt9CiAgICAgICAgZWwoaW50IGEsIFQgYikgewogICAgICAgICAgICB2ZXJ0ZXg9YTsKICAgICAgICAgICAgY29zdD1iOwogICAgICAgIH0KICAgICAgICBib29sIG9wZXJhdG9yIDwoY29uc3QgZWwgJmEpIGNvbnN0IHsKICAgICAgICAgICAgcmV0dXJuIGNvc3Q+YS5jb3N0OwogICAgICAgIH0KICAgIH07CiAgICBpbnQgbjsKICAgIHZlY3RvciA8IHZlY3RvciA8IGVkZ2UgPiA+IHY7CiAgICB2b2lkIGluaXRpYWxpemUoaW50IGspIHsKICAgICAgICBuPWs7CiAgICAgICAgdi5hc3NpZ24obisxLHZlY3RvciA8IGVkZ2UgPiAoKSk7CiAgICB9CiAgICB2b2lkIGFkZF9lZGdlKGludCBmcm9tLCBpbnQgdG8sIFQgdykgewogICAgICAgIHZbZnJvbV0ucHVzaF9iYWNrKGVkZ2UodG8sdykpOwogICAgfQogICAgdm9pZCBydW4oaW50IHN0YXJ0LCB2ZWN0b3IgPCBUID4gKmRpc3QsIGludCBrKSB7CiAgICAgICAgaW50IGksdG87CiAgICAgICAgVCBjdXJyZW50X2Rpc3RhbmNlLHc7CiAgICAgICAgZWwgY3VycjsKICAgICAgICBwcmlvcml0eV9xdWV1ZSA8IGVsID4gcTsKICAgICAgICBmb3IoaT0xO2k8PW47aSsrKSBkaXN0W2ldLmNsZWFyKCk7CiAgICAgICAgcS5wdXNoKGVsKHN0YXJ0LDApKTsKICAgICAgICB3aGlsZSghcS5lbXB0eSgpKSB7CiAgICAgICAgICAgIGN1cnI9cS50b3AoKTsKICAgICAgICAgICAgcS5wb3AoKTsKICAgICAgICAgICAgaWYoKGludCkoZGlzdFtjdXJyLnZlcnRleF0uc2l6ZSgpKT49aykgY29udGludWU7CiAgICAgICAgICAgIGlmKGN1cnIuY29zdD4wKSBkaXN0W2N1cnIudmVydGV4XS5wdXNoX2JhY2soY3Vyci5jb3N0KTsKICAgICAgICAgICAgZm9yKGk9MDtpPChpbnQpKHZbY3Vyci52ZXJ0ZXhdLnNpemUoKSk7aSsrKSB7CiAgICAgICAgICAgICAgICB0bz12W2N1cnIudmVydGV4XVtpXS50bzsKICAgICAgICAgICAgICAgIGlmKChpbnQpKGRpc3RbdG9dLnNpemUoKSk+PWspIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgdz12W2N1cnIudmVydGV4XVtpXS53OwogICAgICAgICAgICAgICAgY3VycmVudF9kaXN0YW5jZT13K2N1cnIuY29zdDsKICAgICAgICAgICAgICAgIHEucHVzaChlbCh0byxjdXJyZW50X2Rpc3RhbmNlKSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn07CgppbnQgdGVzdHMsY3VycmVudF9jYXNlOwppbnQgbixtOwpkaWprc3RyYV9rdGhfc2hvcnRlc3RfcGF0aCA8IGludCwgMTAwMDAwMDAwNyA+IGQ7CnZlY3RvciA8IGludCA+IGRpc3RbTl1bTl07CmludCBxOwoKdm9pZCBtZXNzYWdlKGludCBjdXJyZW50X2Nhc2UpIHsKICAgIC8vY2Vycjw8IkNhc2UgIjw8Y3VycmVudF9jYXNlPDwiIHNvbHZlZCEiPDxlbmRsOwogICAgZnByaW50ZihzdGRlcnIsICJDYXNlICVkIHNvbHZlZCFcbiIsIGN1cnJlbnRfY2FzZSk7Cn0KCgoKaW50IG1haW4oKSB7CiAgICAvL2lvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgLy9jaW4udGllKE5VTEwpOwogICAgaW50IGkseCx5LHo7CgogICAgdGVzdHM9MTsKICAgIC8vc2NhbmYoIiVkIiwgJnRlc3RzKTsKICAgIC8vY2luPj50ZXN0czsKICAgIGZvcihjdXJyZW50X2Nhc2U9MTtjdXJyZW50X2Nhc2U8PXRlc3RzO2N1cnJlbnRfY2FzZSsrKSB7CiAgICAgICAgc2NhbmYoIiVkICVkIiwgJm4sICZtKTsKICAgICAgICBkLmluaXRpYWxpemUobik7CiAgICAgICAgZm9yKGk9MTtpPD1tO2krKykgewogICAgICAgICAgICBzY2FuZigiJWQgJWQgJWQiLCAmeCwgJnksICZ6KTsKICAgICAgICAgICAgZC5hZGRfZWRnZSh4LHkseik7CiAgICAgICAgfQogICAgICAgIGZvcihpPTE7aTw9bjtpKyspIHsKICAgICAgICAgICAgZC5ydW4oaSxkaXN0W2ldLDEwMCk7CiAgICAgICAgfQogICAgICAgIHNjYW5mKCIlZCIsICZxKTsKICAgICAgICB3aGlsZShxLS0pIHsKICAgICAgICAgICAgc2NhbmYoIiVkICVkICVkIiwgJngsICZ5LCAmeik7CiAgICAgICAgICAgIGlmKChpbnQpKGRpc3RbeF1beV0uc2l6ZSgpKTx6KSB7CiAgICAgICAgICAgICAgICBwcmludGYoIi0xXG4iKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIHByaW50ZigiJWRcbiIsIGRpc3RbeF1beV1bei0xXSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIE1FU1NBR0U6CiAgICAgICAgbWVzc2FnZShjdXJyZW50X2Nhc2UpOwogICAgfQoKICAgIHJldHVybiAwOwp9