//itisalways42
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
typedef pair<LL,LL> II;
typedef vector< II > VII;
typedef vector<int> VI;
typedef vector< VI > VVI;
typedef vector< VII > mat;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))
#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
const int N = int(500)+10;
const LL INF = LL(1e15);
const LL MOD = LL(1e9)+7;
int n;
int g[N][N];
void mult(mat &a, mat &b)
{
mat ret(n,VII(n,MP(INF,0)));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
LL mn=INF;
for(int k=0; k<n; k++)
if(a[i][k].F + b[k][j].F < mn)
mn = a[i][k].F + b[k][j].F;
ret[i][j].F = mn;
for(int k=0; k<n; k++)
if(a[i][k].F + b[k][j].F == mn)
ret[i][j].S = (ret[i][j].S + a[i][k].S*b[k][j].S)%MOD;
}
a = ret;
}
mat ret;
void expo(int k)
{
ret.resize(n, VII(n, MP(INF, 0)));
for(int i=0; i<n; i++) ret[i][i] = MP(0,1);
mat a(n,VII(n));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(g[i][j])
a[i][j] = MP(g[i][j],1);
else
a[i][j] = MP(INF,0);
while(k)
{
if(k&1) mult(ret,a);
mult(a,a);
k /= 2;
}
}
int main()
{
fast_io;
int m,k;
cin>>n>>m>>k;
for(int i=0; i<m; i++)
{
int u,v,w;
cin>>u>>v>>w;
u--, v--;
g[u][v] = g[v][u] = w;
}
expo(k);
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(ret[i][j].F == INF) cout<<"X "<<0<<" ";
else cout<<ret[i][j].F<<" "<<ret[i][j].S<<" ";
}
cout<<"\n";
}
return 0;
}
Ly9pdGlzYWx3YXlzNDIKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgCUxMOwp0eXBlZGVmIHBhaXI8TEwsTEw+ICAgSUk7CnR5cGVkZWYgdmVjdG9yPCBJSSA+ICAgICAgVklJOwp0eXBlZGVmIHZlY3RvcjxpbnQ+ICAgICBWSTsKdHlwZWRlZiB2ZWN0b3I8IFZJID4gCVZWSTsKdHlwZWRlZiB2ZWN0b3I8IFZJSSA+IG1hdDsKCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgU1ooYSkgKGludCkoYS5zaXplKCkpCiNkZWZpbmUgQUxMKGEpIGEuYmVnaW4oKSxhLmVuZCgpCiNkZWZpbmUgU0VUKGEsYikgbWVtc2V0KGEsYixzaXplb2YoYSkpCgojZGVmaW5lIHNpKG4pIHNjYW5mKCIlZCIsJm4pCiNkZWZpbmUgZG91dChuKSBwcmludGYoIiVkXG4iLG4pCiNkZWZpbmUgc2xsKG4pIHNjYW5mKCIlbGxkIiwmbikKI2RlZmluZSBsbGRvdXQobikgcHJpbnRmKCIlbGxkXG4iLG4pCiNkZWZpbmUgZmFzdF9pbyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKE5VTEwpCgojZGVmaW5lIFRSQUNFCgojaWZkZWYgVFJBQ0UKI2RlZmluZSB0cmFjZSguLi4pIF9fZigjX19WQV9BUkdTX18sIF9fVkFfQVJHU19fKQp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMT4Kdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZSwgQXJnMSYmIGFyZzEpewoJY2VyciA8PCBuYW1lIDw8ICIgOiAiIDw8IGFyZzEgPDwgc3RkOjplbmRsOwp9CnRlbXBsYXRlIDx0eXBlbmFtZSBBcmcxLCB0eXBlbmFtZS4uLiBBcmdzPgp2b2lkIF9fZihjb25zdCBjaGFyKiBuYW1lcywgQXJnMSYmIGFyZzEsIEFyZ3MmJi4uLiBhcmdzKXsKCWNvbnN0IGNoYXIqIGNvbW1hID0gc3RyY2hyKG5hbWVzICsgMSwgJywnKTtjZXJyLndyaXRlKG5hbWVzLCBjb21tYSAtIG5hbWVzKSA8PCAiIDogIiA8PCBhcmcxPDwiIHwgIjtfX2YoY29tbWErMSwgYXJncy4uLik7Cn0KI2Vsc2UKI2RlZmluZSB0cmFjZSguLi4pCiNlbmRpZgoKLy9GSUxFICpmaW4gPSBmcmVvcGVuKCJpbiIsInIiLHN0ZGluKTsKLy9GSUxFICpmb3V0ID0gZnJlb3Blbigib3V0IiwidyIsc3Rkb3V0KTsKCmNvbnN0IGludCBOID0gaW50KDUwMCkrMTA7CmNvbnN0IExMIElORiA9IExMKDFlMTUpOwpjb25zdCBMTCBNT0QgPSBMTCgxZTkpKzc7CmludCBuOwppbnQgZ1tOXVtOXTsKCnZvaWQgbXVsdChtYXQgJmEsIG1hdCAmYikKewoJbWF0IHJldChuLFZJSShuLE1QKElORiwwKSkpOwoJZm9yKGludCBpPTA7IGk8bjsgaSsrKQoJCWZvcihpbnQgaj0wOyBqPG47IGorKykKCQl7CgkJCUxMIG1uPUlORjsKCQkJZm9yKGludCBrPTA7IGs8bjsgaysrKQoJCQkJaWYoYVtpXVtrXS5GICsgYltrXVtqXS5GIDwgbW4pCgkJCQkJbW4gPSBhW2ldW2tdLkYgKyBiW2tdW2pdLkY7CgkJCXJldFtpXVtqXS5GID0gbW47CgkJCWZvcihpbnQgaz0wOyBrPG47IGsrKykKCQkJCWlmKGFbaV1ba10uRiArIGJba11bal0uRiA9PSBtbikKCQkJCQlyZXRbaV1bal0uUyA9IChyZXRbaV1bal0uUyArIGFbaV1ba10uUypiW2tdW2pdLlMpJU1PRDsKCQl9CglhID0gcmV0Owp9CgptYXQgcmV0Owp2b2lkIGV4cG8oaW50IGspCnsKCXJldC5yZXNpemUobiwgVklJKG4sIE1QKElORiwgMCkpKTsKCglmb3IoaW50IGk9MDsgaTxuOyBpKyspIHJldFtpXVtpXSA9IE1QKDAsMSk7CgltYXQgYShuLFZJSShuKSk7Cglmb3IoaW50IGk9MDsgaTxuOyBpKyspCgkJZm9yKGludCBqPTA7IGo8bjsgaisrKQoJCQlpZihnW2ldW2pdKQkKCQkJCWFbaV1bal0gPSBNUChnW2ldW2pdLDEpOwoJCQllbHNlCQoJCQkJYVtpXVtqXSA9IE1QKElORiwwKTsKCXdoaWxlKGspCgl7CgkJaWYoayYxKSBtdWx0KHJldCxhKTsKCQltdWx0KGEsYSk7CgkJayAvPSAyOwoJfQp9CgppbnQgbWFpbigpCnsKCWZhc3RfaW87CglpbnQgbSxrOwoJY2luPj5uPj5tPj5rOwoJZm9yKGludCBpPTA7IGk8bTsgaSsrKQoJewoJCWludCB1LHYsdzsKCQljaW4+PnU+PnY+Pnc7CgkJdS0tLCB2LS07CgkJZ1t1XVt2XSA9IGdbdl1bdV0gPSB3OwoJfQoJZXhwbyhrKTsKCWZvcihpbnQgaT0wOyBpPG47IGkrKykKCXsKCQlmb3IoaW50IGo9MDsgajxuOyBqKyspCgkJewoJCQlpZihyZXRbaV1bal0uRiA9PSBJTkYpIGNvdXQ8PCJYICI8PDA8PCIgIjsKCQkJZWxzZSBjb3V0PDxyZXRbaV1bal0uRjw8IiAiPDxyZXRbaV1bal0uUzw8IiAiOwoJCX0KCQljb3V0PDwiXG4iOwoJfQoJcmV0dXJuIDA7Cn0K