题意：

给一张有向图，q个询问，询问s到t至少经过k条路的最近距离。

题解：
f[k][i][j]表示从i到j经过k条路的最短路，则f[k][i][j]=min{f[k-1][i][t]+map[t][j]},(1<=t<=n),这个方程很好理解，从i到j经过k条路，我们枚举中间点t，从i到t经过k-1条，从t到j经过1条，取最短的就是从i到j经过k条。

一般的，还有f[k][i][j]=min{f[k-x][i][t]+f[x][t][j]},我们将这种操作定义为f[k-x]的图与f[x]的图的合并。

现在，对于每一个询问，迭代合并k-1次即可以求解，但时间显然是无法接受的，这里考虑分块的思想。

路径的条数最多10000，我们将k拆分成100p+q的形式，其中 p、q都小于100，我们首先预处理出f[1],f[2]......f[100]的图，再预处理出f[100],f[200],f[300]......f[10000]的图，这样对于每个k，枚举中间的x，min{f[100p][s][x]+f[q][x][t]}就是从s到t恰好经过k条路的最短路。

题目要求是至少经过k条路，我们将 f[k][i][j]=min{f[k][i][j],f[k+1][i][j]}，从后向前过一遍就是至少经过k条路的最短路了，这是显然的。

注意，当q接近100时，比如k=199，此时假设最短路要经过202条路径，我们这样是无法求解的，因为之前的条件时q<100,而正解的方案是 100(p=1)+102(q=99)，我们意识到给出的k，正解一定是在[k,k+n]的范围内，因为k足够大时，正解的路径一定是在重复走一个环，而环的边数一定小于n，所以最多走k+n步。我们只需将f[101],f[102]...f[105]的图多求出来即可。

代码：

#include<bits/stdc++.h>
#define N 50
#define INF 1e9
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define eps 1e-8
const LL P=1e9+7;
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int n;
struct M{
    int m[N][N];
    M()
    {
        memset(this,0x3f,sizeof (M));
    }
    friend M operator * (M& a, M& b){
        M c;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
            {
                for (int k=0; k<n; k++)
                    c.m[i][k]=min(c.m[i][k],a.m[i][j]+b.m[j][k]);
            }
        return c;
    }
};

int a[102][N][N],b[152][N][N];

int main()
{
    IO
    int T;
    cin>>T;
    while(T--)
    {
        int m,q,j,k,l; M f;
        cin>>n>>m;
        for (int i=1;i<=m;i++)
        {
            cin>>j>>k>>l; j--;k--;
            f.m[j][k]=min(f.m[j][k],l);
        }
        M f2;
        for (int i=0;i<n;i++) for (int j=0;j<n;j++)  if (i==j) f2.m[i][j]=0;else f2.m[i][j]=INF;
        for (int j=0;j<n;j++) for (int k=0;k<n;k++)
            if (j==k) a[0][j][k]=b[0][j][k]=0;else a[0][j][k]=b[0][j][k]=INF;

        for (int i=1;i<=150;i++)
        {
            f2=f2*f;
            for (int j=0;j<n;j++)
                for (int k=0;k<n;k++) b[i][j][k]=f2.m[j][k];
        }
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++) f2.m[i][j]=b[100][i][j];
        M f3;
        for (int i=0;i<n;i++) for (int j=0;j<n;j++)  if (i==j) f3.m[i][j]=0;else f3.m[i][j]=INF;
        for (int i=1;i<=100;i++)
        {
            f3=f3*f2;
            for (int j=0;j<n;j++)
                for (int k=0;k<n;k++) a[i][j][k]=f3.m[j][k];
        }

        for (int i=149;~i;i--)
        {
            for (int j=0;j<n;j++)
                for (int k=0;k<n;k++)
                {
                    b[i][j][k]=min(b[i][j][k],b[i+1][j][k]);
                    if (i<100)a[i][j][k]=min(a[i][j][k],a[i+1][j][k]);
                }
                    
        }
        cin>>q;
        while(q--)
        {
            int s,t,k;
            cin>>s>>t>>k;
            s--;t--;
            int ss=k/100,tt=k%100; int ans=INF;
            for (int i=0;i<n;i++)
            {
                ans=min(ans,a[ss][s][i]+b[tt][i][t]);
            }
            if (ans!=INF)cout<<ans<<endl;else cout<<"-1\n";
        }
    }
    return 0;
}