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

typedef long long ll;
const int mod=998244353;
const int N=2010,M=5010;
const ll inf=1e18;

struct edge{
    int x,y,c,next;
}a[2*M];int len,last[N];

void ins(int x,int y,int c){
    a[++len].x=x;a[len].y=y;a[len].c=c;
    a[len].next=last[x];last[x]=len;
}

ll st[N][4*N],ed[N][4*N];int Ans,n,m,lim;
int Odd1[N],Odd2[N],Even1[N],Even2[N];

struct line{
    ll k,b;int op;
}g[8*M];int tot,sta[8*M],cnt,sum,List[8*M];

bool cmp(int n1,int n2){
    if(g[n1].k==g[n2].k) return (g[n1].b>g[n2].b);
    return (g[n1].k>g[n2].k);
}

ll doit(int x1,int x2){
    if(g[x2].b<=g[x1].b) return 0;
    return (g[x2].b-g[x1].b+g[x1].k-g[x2].k-1)/(g[x1].k-g[x2].k);
}

ll calc(ll L,ll R,int x){
    return (((R-L)/2+1)* (g[x].b%mod) + ((R+L)/2)*((R-L)/2+1)%mod*g[x].k)%mod;
}

void solve(int op){
    tot=0;sum=0;
    for(int i=1;i<=cnt;i++)
        if(g[i].op==op) List[++sum]=i;
    sort(List+1,List+sum+1,cmp);
    for(int i=1;i<=sum;i++){
        if(i<sum&&g[List[i]].k==g[List[i+1]].k) continue;
        while(tot>1&&doit(sta[tot-1],sta[tot])>=doit(sta[tot-1],List[i])) tot--;
        sta[++tot]=List[i];
    }

    // for(int i=1;i<=tot;i++) printf("%lld %lld\n",g[sta[i]].k,g[sta[i]].b);

    for(int i=1;i<=tot;i++){
        ll L=4*n+2,R=lim;
        if(i>1) L=max(L,doit(sta[i-1],sta[i]));
        if(i<tot) R=min(R,doit(sta[i],sta[i+1])-1);
        if(L%2!=op) L++;
        if(R%2!=op) R--;
        if(L<=R) Ans=(Ans+calc(L,R,sta[i]))%mod;//,printf("%lld %lld %lld %lld\n",L,R,g[sta[i]].k,g[sta[i]].b);
    }
}

int main()
{

    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&lim);
        len=0;for(int i=1;i<=n;i++) last[i]=0;
        for(int i=1;i<=m;i++){
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            ins(x,y,c);
            ins(y,x,c);
        }

        for(int i=0;i<=4*n+1;i++)
            for(int j=1;j<=n;j++)
                st[j][i]=ed[j][i]=inf;
        st[1][0]=ed[n][0]=0;
        // printf("!!! %d\n",n);
        for(int i=0;i<4*n+1;i++)
            for(int j=1;j<=n;j++)
                for(int k=last[j];k;k=a[k].next){
                    int y=a[k].y;
                    st[y][i+1]=min(st[y][i+1],st[j][i]+a[k].c);
                    ed[y][i+1]=min(ed[y][i+1],ed[j][i]+a[k].c);
                }

        Ans=0;
        for(int i=1;i<=4*n+1&&i<=lim;i++)
            if(st[n][i]!=inf) Ans=(Ans+st[n][i])%mod;

        /*for(int i=1;i<=n;i++){
            int id1=-1,id2=-1,id3=-1,id4=-1;
            for(int j=4*n+1;j>=0;j--){
                if(st[i][j]!=inf){
                    if(j&1) id1=j;
                    else id2=j;
                }

                if(ed[i][j]!=inf){
                    if(j&1) id3=j;
                    else id4=j;
                }
            }
            Odd1[i]=id1; Odd2[i]=id3;
            Even1[i]=id2; Even2[i]=id4;
        }*/

        // printf("%d %d %d %d\n",Odd1[1],Even1[1],Odd2[2],Even2[2]);

        cnt=0;
        for(int i=1;i<=len;i++){
            //id1 + id3 -> dis[id1] + dis[id3]
            int id1=-1,id2=-1,id3=-1,id4=-1;
            for(int j=2*n;j>=0;j--){
                if(st[a[i].x][j]!=inf){
                    if(j&1){
                        if(id1==-1||st[a[i].x][j]-(ll)j*a[i].c<st[a[i].x][id1]-(ll)id1*a[i].c)
                            id1=j;
                    }
                    else{
                        if(id2==-1||st[a[i].x][j]-(ll)j*a[i].c<st[a[i].x][id2]-(ll)id2*a[i].c)
                            id2=j;
                    }
                }

                if(ed[a[i].y][j]!=inf){
                    if(j&1){
                        if(id3==-1||ed[a[i].y][j]-(ll)j*a[i].c<ed[a[i].y][id3]-(ll)id3*a[i].c)
                            id3=j;
                    }
                    else{
                        if(id4==-1||ed[a[i].y][j]-(ll)j*a[i].c<ed[a[i].y][id4]-(ll)id4*a[i].c)
                            id4=j;
                    }
                }
            }
            Odd1[a[i].x]=id1; Odd2[a[i].y]=id3;
            Even1[a[i].x]=id2; Even2[a[i].y]=id4;

            if(Odd1[a[i].x]!=-1&&Odd2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Odd1[a[i].x]]+ed[a[i].y][Odd2[a[i].y]]-(ll)a[i].c*(Odd1[a[i].x]+Odd2[a[i].y]), g[cnt].op=1;

            if(Even1[a[i].x]!=-1&&Even2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Even1[a[i].x]]+ed[a[i].y][Even2[a[i].y]]-(ll)a[i].c*(Even1[a[i].x]+Even2[a[i].y]), g[cnt].op=1;

            if(Odd1[a[i].x]!=-1&&Even2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Odd1[a[i].x]]+ed[a[i].y][Even2[a[i].y]]-(ll)a[i].c*(Odd1[a[i].x]+Even2[a[i].y]), g[cnt].op=0;

            if(Even1[a[i].x]!=-1&&Odd2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Even1[a[i].x]]+ed[a[i].y][Odd2[a[i].y]]-(ll)a[i].c*(Even1[a[i].x]+Odd2[a[i].y]), g[cnt].op=0;
        }

        solve(0);
        solve(1);

        printf("%d\n",Ans);
    }

    return 0;
}