#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod=1e18;
const ll base[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000};
const ll mmd=998244353;

struct Node
{
    ll a[5];

    inline void clear(int op)
    {
        a[0]=a[1]=a[2]=a[3]=a[4]=0;
        if(op)
            a[4]=mod/10;
    }

    inline void print()
    {
        ll rr=0,pk=1;

        for(int i=0;i<5;i++)
        {
            rr=(rr+a[i]%mmd*pk)%mmd;
            pk=mod%mmd*pk%mmd;
        }

        cout<<rr<<' ';
    }
};

Node mx,K,bk[305][305],sum[305][305],res[305],tmp;
__int128 ek=1,qwq[5];
ll ed[305];
int __,_;
int n,m;
char s[75];

inline Node comb(const Node &x,const Node &y)
{
    for(int i=0;i<5;i++)
        tmp.a[i]=x.a[i]+y.a[i];

    for(int i=0;i<4;i++)
    {
        if(tmp.a[i]>=mod)
            tmp.a[i+1]++,tmp.a[i]-=mod;
    }

    return tmp;
}

inline void update(Node &x,const Node &y)
{
    for(int i=4;i;i--)
    {
        if(x.a[i]!=y.a[i])
        {
            if(y.a[i]<x.a[i])
                x=y;
            return;
        }
    }

    if(y.a[0]<x.a[0])
        x=y;
}

inline bool check(const Node &x,ll y){return x.a[1]||x.a[2]||x.a[3]||x.a[4]||x.a[0]>=y;}

inline Node query(int l,int r)
{
    if(l>r)
        swap(l,r);

    tmp.clear(0);

    for(int i=l+1;i<=r;i++)
    {
        tmp.a[0]+=ed[i];
        if(tmp.a[0]>=mod)
            tmp.a[1]++,tmp.a[0]-=mod;
    }

    return tmp;
}

inline Node qmin(const Node &x,ll y)
{
    tmp=x;
    tmp.a[0]-=y;
    for(int i=0;i<4;i++)
    {
        if(tmp.a[i]<0)
        {
            tmp.a[i+1]--;
            tmp.a[i]+=mod;
        }
    }

    return tmp;
}

inline Node tmk(const Node &x,ll y)
{
    for(int i=0;i<5;i++)
        qwq[i]=ek*x.a[i]*y;

    for(int i=0;i<4;i++)
    {
        qwq[i+1]+=qwq[i]/mod;
        tmp.a[i]=qwq[i]%mod;
    }
    tmp.a[4]=qwq[4];

    return tmp;
}

inline void sol()
{
    cin>>n>>m>>(s+1);
    int len=strlen(s+1);

    for(int i=0;i<5;i++)
    {
        int p=0;
        ll tp=0;
        while(p<18&&len)
        {
            tp+=(s[len]-'0')*base[p];
            p++,len--;
        }
        K.a[i]=tp;
    }

    if(__==2)
    {
        while(m--)
        {
            int u,v;
            ll w;
            cin>>u>>v>>w;
            if(u<v)
                ed[v]=w;
        }

        for(int i=1;i<=n;i++)
        {
            if((i&1)!=(K.a[0]&1))
            {
                cout<<-1<<' ';
                continue;
            }

            res[0].clear(1);

            for(int j=2;j<=n;j++)
            {
                if(check(K,j-1+abs(i-j)))
                    update(res[0],comb(tmk(qmin(K,j-1+abs(i-j)),ed[j]),comb(query(1,j),query(i,j))));
            }

            if(res[0].a[4]>=mod/10)
                cout<<"-1 ";
            else
                res[0].print();
        }

        cout<<'\n';

        return;
    }

    for(int i=1;i<=n;i++)
    {
        res[i].clear(1);
        for(int j=1;j<=n;j++)
            bk[i][j].clear(1);
    }
    res[1].clear(0);

    while(m--)
    {
        int u,v;
        ll w;
        cin>>u>>v>>w;

        if(check(bk[u][v],w))
        {
            bk[u][v].clear(0);
            bk[u][v].a[0]=w;
            if(bk[u][v].a[0]>=mod)
                bk[u][v].a[1]++,bk[u][v].a[0]-=mod;
        }
    }

    while(check(K,1))
    {
        if(K.a[0]&1)
        {
            for(int i=1;i<=n;i++)
            {
                sum[0][i].clear(1);
                for(int j=1;j<=n;j++)
                    update(sum[0][i],comb(res[j],bk[j][i]));
            }

            for(int i=1;i<=n;i++)
                res[i]=sum[0][i];
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                sum[i][j].clear(1);
                for(int k=1;k<=n;k++)
                    update(sum[i][j],comb(bk[i][k],bk[k][j]));
            }
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                bk[i][j]=sum[i][j];
        }

        for(int i=4;i;i--)
        {
            if(K.a[i]&1)
                K.a[i-1]+=mod;
            K.a[i]>>=1;
        }
        K.a[0]>>=1;
    }

    for(int i=1;i<=n;i++)
    {
        if(res[i].a[4]>=mod/10)
            cout<<"-1 ";
        else
            res[i].print();
    }

    cout<<'\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    mx.clear(1);

    cin>>__>>_;
    while(_--)
        sol();

    return 0;
}