#include <cassert>
#include <iostream>
#include <functional>
#include <iomanip>
#include <set>
#include <numeric>
#include <unordered_map>
#include <map>
#include <queue>
#include <stack>
#include <complex>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath> 
#include <random>
#include <vector>

using namespace std;

using LL = long long;

const int base = 998244353;
const int MAX = 60; 

using PII = pair<LL, LL>;

struct Node {
    int a, b;
    Node operator + (const Node & g) {
        Node f {(a+g.a)% base, (b+g.b) % base};
        return f;
    }

    Node operator * (const Node & g) {
        Node f;
        f.a = (LL(a) * g.a  + LL(b) * g.b ) % base ;
        f.b = (LL(a) * g.b  + LL(b) * g.a ) % base ;
        return f;
    }
};

class Matrix {
    int n0, m0;
    using INT = Node;
    LL bbase;
public:
    using LINE = vector<INT>;
    vector< LINE > d0;
    Matrix(int n_, int m_) : n0(n_), m0(m_) {
        d0.resize(n0, LINE(m0));
        bbase = base;
    }
    static Matrix eye(int n) {
        Matrix a(n, n);
        for (int i = 0; i < n; ++i) {
            a.d0[i][i] = {1,0};
        }
        return move(a);
    }
    Matrix operator * (const Matrix & b) {
        assert(m0 == b.n0);
        Matrix c(n0, b.m0);
        auto & d1 = b.d0;
        auto & d = c.d0;
        for (int i = 0; i < n0; ++i) {
            for (int j = 0; j < b.m0; ++j) {
                for (int k = 0; k < m0; ++k) {
                    d[i][j] = d[i][j] +  d0[i][k] * d1[k][j];
                }
            }
        }
        return move(c);
    }
    Matrix pow(LL k) {
        assert(n0 == m0);
        Matrix c = eye(n0);
        Matrix g = *this;
        while (k > 0) {
            if (k % 2 == 1) {
                c = c* g;
            }
            k /= 2;
            g = g*g;
        }
        return move(c);
    }
    LINE mul(LINE v) {
        assert(v.size() == m0);
        LINE v0(n0);
        for (int i = 0; i < n0; ++i) {
            for (int j = 0; j < m0; ++j) {
                v0[i] = v0 [i] +  d0[i][j] * v[j];
            }
        }
        return move(v0);
    }
    LINE left_mul(LINE v) {
        assert(v.size() == n0);
        LINE v0(m0);
        for (int j = 0; j < m0; ++j) {
            for (int i = 0; i < n0; ++i) {
                v0[j] = v0[j] +  d0[i][j] * v[i];
            }
        }
        return move(v0);
    }

    static Matrix recursive(LINE v) {
                // f(n) = Σ bi * f(i),  i= 0... n-1
        // v :  b0, b1,  ... bn-1
                // u :  f(n-1), f(n-2)... f(0)
                //  M * u.T
        int y = v.size();
        Matrix t(y, y);
        auto & d = t.d0;
        for (int i = 0; i < y; ++i) {
            d[0][i] = v[y - 1 - i];
        }
        for (int i = 1; i < y; ++i) {
            d[i][i - 1] = {1, 0};
        }
        return move(t);
    }
};



LL e_gcd(LL a, LL b, LL &x, LL &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL ans = e_gcd(b, a%b, x, y);
    LL temp = x;
    x = y;
    y = temp - a / b*y;
    return ans;
}



// find x  while  a*x % b ==c 
LL cal_mod(LL a, LL b, LL c)
{
    LL x, y;
    LL gcd = e_gcd(a, b, x, y);
    if (c%gcd != 0) return -1;
    x *= c / gcd;
    b /= gcd;
    if (b<0) b = -b;
    LL ans = x%b;
    if (ans <= 0) ans += b;
    return ans;
}

// find x  while  a*x % m ==1 
LL cal_inv(LL a, LL m = base) {
    LL x, y;
    LL gcd = e_gcd(a, m, x, y);
    assert(gcd == 1);
    LL ans = x%m;
    if (ans <= 0) ans += m;
    assert(ans *a %m == 1);
    return ans;
}
LL qexp(LL x, LL k, LL base_ = base) {
    assert(x >= 0);
    if (k == 0) return 1;
    LL r = 1, t = x%base_;
    while (k>0) {
        if (k & 1) r = (r*t) % base_;
        k >>= 1;
        t = (t*t) % base_;
    }
    return r;
}

void solve() {
    int n,m,k;
    cin >> n >>m >>k;
    vector<PII> gp[110];
    for (int i=0; i<m; ++i) {
        int a, b, c;
        cin >>a>>b>>c;
        gp[a].push_back( {b,c});
        gp[b].push_back( {a,c});
    }
    Matrix mx(n,n);
    for (int i=1; i<=n; ++i) {
        if (gp[i].empty()) continue;
        int inv = cal_inv(gp[i].size());
        for (auto g: gp[i]) {
            Node x = {inv, 0};
            if (g.second) x = {0,inv};
            mx.d0[g.first-1][i-1] = x;
        }
    }
    auto mx1 = mx.pow(k);
    Matrix::LINE v(n);
    v[0] = {1,0};
    auto v1 = mx1.mul(v);
    int r = v1[n-1].b;
    cout<<r<<'\n';
}
 

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //int a = getct(gap + 123);
    //int b = getct2(gap+123);
    int T;
    cin >>T;
    for (int tp=0; tp<T; ++tp) {
        solve();
    }

}