简单矩阵乘法
可以矩阵套矩阵，也可以只建一个矩阵
std写得是矩阵套矩阵的写法

第一个矩阵（最大的矩阵）

矩阵大小:
矩阵意义：对于代表从i走到j需要的最少体力
矩阵嵌套：对于是一个小矩阵，小矩阵定义参见下方

第二个矩阵（小矩阵）

矩阵大小：
矩阵意义：对于代表走过新路的第i条到第j条的最少体力

矩阵转移

见代码

std

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a,b;
struct ppp {
    long long f[12][12];
    ppp operator*(const ppp x) {
        ppp y;
        memset(y.f,10,sizeof(y.f));
        for(long long i=0; i<=b; i++)
            for(long long j=i; j<=b; j++)
                for(long long k=i; k<=j; k++)
                    y.f[i][j]=min(y.f[i][j],f[i][k]+x.f[k][j]);
        return y;
    }
};
ppp Min(ppp x,ppp y) {
    for(long long i=0; i<=b; i++)
        for(long long j=0; j<=b; j++)
            x.f[i][j]=std::min(x.f[i][j],y.f[i][j]);
    return x;
}
struct oppo {
    ppp f[30][30];
    oppo operator*(const oppo x) {
        oppo y;
        memset(y.f,10,sizeof(y.f));
        for(long long k=1; k<=n; k++)
            for(long long i=1; i<=n; i++)
                for(long long j=1; j<=n; j++)
                    y.f[i][j]=Min(f[i][k]*x.f[k][j],y.f[i][j]);
        return y;
    }
} cs,ans;
void ksm(long long g) {
    memset(ans.f,10,sizeof(ans.f));
    for(long long i=1; i<=n; i++)
        ans.f[i][i].f[0][0]=0;
    while(g) {
        if(g&1) ans=ans*cs;
        g>>=1;
        cs=cs*cs;
    }
    long long st=LONG_LONG_MAX;
    for(long long j=1; j<=n; j++)
        st=min(st,ans.f[1][j].f[0][b]);
    if(st!=ans.f[0][0].f[0][0]) cout<<st<<"\n";
    else puts("-1");
}
int main() {
    cin>>n>>m>>k>>a>>b;
    memset(cs.f,10,sizeof(cs.f));
    for(long long i=1; i<=m; i++) {
        long long s,t,u;
        scanf("%lld%lld%lld",&s,&t,&u);
        for(long long j=0; j<=b; j++)
            cs.f[s][t].f[j][j]=u;
    }
    for(long long i=1; i<=a; i++) {
        long long s,t,u;
        scanf("%lld%lld",&s,&t);
        for(long long j=1; j<=b; j++) {
            scanf("%lld",&u);
            cs.f[s][t].f[j-1][j]=u;
        }
    }
    ksm(k+b);
    return 0;
}