https://codeforces.com/gym/102644/problem/F

/*
* @Author: dnhirapara
*/
#include <bits/stdc++.h>

using namespace std;

/************defination************/

#define endl "\n"
#define log(x) cout << __LINE__ << ": " << #x << " -> " << (x) << endl;
#define ll long long int
#define ull unsigned long long int
const long long int MOD = 1e9 + 7;

class Matrix
{
public:
    vector<vector<ll>> mat;
    ll row, column;
    bool square_mat = false;

    Matrix(vector<vector<ll>> &a)
    {
        mat = a;
        this->row = a.size();
        this->column = a[0].size();
    }

    Matrix(ll same = 2)
    {
        square_mat = true;
        this->column = same;
        this->row = same;
        mat.resize(row, vector<ll>(column, 1e10));
    }

    Matrix(ll row, ll column)
    {
        if (row == column)
            square_mat = true;
        this->row = row;
        this->column = column;
        mat.resize(row, vector<ll>(column, 1e10));
    }
    pair<ll, ll> get_size()
    {
        // cout << row << " " << column << endl;
        return make_pair(row, column);
    }
    void make_identity()
    {
        for (ll i = 0; i < row; i++)
        {
            for (ll j = 0; j < column; j++)
            {
                mat[i][j] = i == j;
            }
        }
    }
    void make_inf(ll inf = LLONG_MAX)
    {
        for (ll i = 0; i < row; i++)
        {
            for (ll j = 0; j < column; j++)
            {
                mat[i][j] = inf;
            }
        }
    }
    void make_val(ll val = 0)
    {
        for (ll i = 0; i < row; i++)
        {
            for (ll j = 0; j < column; j++)
            {
                mat[i][j] = val;
            }
        }
    }
    Matrix operator+(Matrix m)
    {
        if (this->row != m.row || this->column != m.column)
        {
            cerr << "Matrix : In addition operation both matrix should be of same dimension..." << endl;
            exit(0);
        }
        Matrix res(m.row, m.column);
        for (ll i = 0; i < m.row; i++)
        {
            for (ll j = 0; j < m.column; j++)
            {
                res.mat[i][j] = m.mat[i][j] + this->mat[i][j];
            }
        }
        return res;
    }

    Matrix operator%(ll mod)
    {
        if (mod <= 0)
        {
            cerr << "Invalid mod value..."
                 << "\n";
            exit(0);
        }
        Matrix res(row, column);
        for (ll i = 0; i < this->row; i++)
        {
            for (ll j = 0; j < this->column; j++)
            {
                res.mat[i][j] = (mat[i][j]) % mod;
            }
        }
        return res;
    }

    Matrix operator*(const Matrix &m)
    {
        if (this->column != m.row)
        {
            cerr << "Matrix : In multplication operation first matrix column and seocnd matrix row should be same ..." << endl;
            exit(0);
        }
        Matrix res(this->row, m.column);
        for (ll i = 0; i < this->row; i++)
        {
            for (ll j = 0; j < m.column; j++)
            {
                cout << "j" << endl;
                for (ll k = 0; k < m.row; k++)
                {
                    ll temp = this->mat[i][k] + m.mat[k][j];
                    cout << temp << endl;
                    cout << res.mat[i][j] << endl;
                    res.mat[i][j] = min(res.mat[i][j], temp);
                    cout << "mini :" << res.mat[i][j] << endl;
                }
            }
        }
        return res;
    }

    Matrix multi()
    {
        return mat;
    }

    vector<ll> &operator[](ll i)
    {
        return mat[i];
    }

    void printMat()
    {
        for (ll i = 0; i < row; i++)
        {
            for (ll j = 0; j < column; j++)
            {
                cout << mat[i][j] << " ";
            }
            cout << "\n";
        }
    }

private:
    void add(ll &a, ll b)
    {
        a = b;
    }
    ll mul(ll a, ll b)
    {
        return min(a, b);
    }
};

// Matrix pre[32];

// void init(Matrix &mat)
// {
//     pre[0].make_identity();
//     pre[1] = mat;
//     for (ll i = 2; i < 32; ++i)
//     {
//         pre[i] = pre[i - 1] * pre[i - 1];
//     }
// }

// Matrix power(Matrix &a, long long x)
// {
//     init(a);
//     Matrix res;
//     res.make_identity();
//     ll cnt = 1;
//     while (x)
//     {
//         if (x & 1)
//         {
//             res = res * pre[cnt];
//         }
//         cnt += 1;
//         x >>= 1;
//     }
//     return res;
// }

Matrix power(Matrix a, long long x)
{
    Matrix res(a.row, a.column);
    res.make_val(1e10);
    while (x)
    {
        if (x & 1)
        {
            res = res * a;
            cout << "@@@@@@@@@@@@@@@@printres@@@@@@@@@@@@@@@@@@" << endl;
            res.printMat();
            cout << "printend" << endl;
        }
        a = a * a;
        cout << "print a" << endl;
        a.printMat();
        cout << "printend" << endl;
        x >>= 1;
    }
    return res;
}

//@time comp :
//@space comp :
int main()
{
    // ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cin.ignore(); must be there when using getline(cin, s)
    ll tc = 1;
    // cin >> tc;
    while (tc--)
    {
        ll n, m, k;
        cin >> n >> m >> k;
        ll weight;
        Matrix mat(n, n);
        ll x, y;
        for (ll i = 0; i < n; i++)
        {
            for (ll j = 0; j < n; j++)
            {
                mat[i][j] = 1e10;
            }
        }
        for (ll i = 0; i < m; i++)
        {
            cin >> x >> y >> weight;
            mat[x - 1][y - 1] = weight;
        }
        // power(mat,k).printMat();
        ll ans = 0;
        Matrix ansmat = power(mat, k);
        ansmat.printMat();
    }
    return 0;
}