#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5000+5,M=N*120+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,type,k;
int X[N*2],Y[N*2],Z[N*2];
vector<int> S[N];
int scc[N];
namespace Tarjan{
	int dfn[N],low[N],dh,st[N],sh;
	void tarjan(int x){
		dfn[x]=low[x]=++dh;st[++sh]=x;
		for(int i:S[x]){
			if(!dfn[i]) tarjan(i),low[x]=min(low[x],low[i]);
			else if(!scc[i]) low[x]=min(low[x],dfn[i]);
		}
		if(low[x]==dfn[x]){
			++k;
			while(st[sh+1]^x) scc[st[sh]]=k,sh--;	
		}
	}
	void build(){
		for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	}
}
vector<int> V[N],G1[N],G2[N];
bitset<101> g1[N][101],g2[N][101];
int w[N];
int qryGCD(int x){
	static int dis[N];
	for(int i=101;i;i--){
		for(int j:V[x]) dis[j]=-1;
		dis[V[x][0]]=0;
		queue<int> q;
		q.push(V[x][0]);
		int flag=0;
		while(!q.empty()){
			int x=q.front();q.pop();
			for(int j:G1[x]){
				int y=Y[j];
				if(~dis[y]){
					if(dis[y]!=(dis[x]+Z[j])%i) {flag=1;break;}
				}else dis[y]=(dis[x]+Z[j])%i,q.push(y);
			}
		}
		if(!flag) return i;
	}
	return 0;
}
void dfs1(int x,int a,int b){
	if(g1[x][a][b]) return;
	g1[x][a][b]=1;
	for(int i:G2[x]) dfs1(Y[i],a,(b+Z[i])%a);
}
void dfs2(int x,int a,int b){
	if(w[scc[x]]^101) a=__gcd(a,w[scc[x]]),b%=a;
	if(g2[x][a][b]) return;
	if(x==n) gdb(x,a,b);
	g2[x][a][b]=1;
	for(int i:G2[x]) dfs2(Y[i],a,(b+Z[i])%a);
}
namespace BigInt{
	int k,ans[N];
	void init(){
		k=0;ans[0]=1;
	}
	void mul(int x){
		int w=0;
		for(int i=k;~i;i--) w=(w*10+ans[i])%x;
		x/=__gcd(w,x);
		for(int i=0;i<=k;i++) ans[i]*=x;
		for(int i=0;i<k;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
		while(ans[k]>=10) ans[k+1]=ans[k]/10,ans[k]%=10,k++;
	}
	void print(){
		ll w=0;
		const int mod=1e9+9;
		for(int i=k;~i;i--) w=(w*10+ans[i])%mod;
		printf("%lld\n",w);
	}
}
bitset<105> g[105],vis[105];
int flag[N*4],pr[N*4],ph;
void initprim(){
	const int n=2e4;
	for(int i=2;i<=n;i++) {
		if(!flag[i]) pr[++ph]=i;
		for(int j=1;j<=ph&&i*pr[j]<=n;j++){
			flag[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
}
void Solve(){
	scanf("%d%d%d",&n,&m,&type);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
		S[X[i]].push_back(Y[i]);
	}
	Tarjan::build();
	for(int i=1;i<=m;i++){
		if(scc[X[i]]==scc[Y[i]]) G1[X[i]].push_back(i);
		G2[X[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) V[scc[i]].push_back(i);
	for(int i=1;i<=k;i++) w[i]=qryGCD(i),gdb(w[i]);
	for(int i=1;i<=100;i++) dfs1(1,i,0);
	for(int i=1;i<=n;i++) if(w[scc[i]]^101){
		for(int y=0;y<w[scc[i]];y++) if(g1[i][w[scc[i]]][y]) dfs2(i,w[scc[i]],y);
	}
	BigInt::init();
	for(int x=1;x<=100;x++) for(int y=0;y<x;y++) g[x][y]=g2[n][x][y];

	for(int x=1;x<=100;x++){
		for(int y=0;y<x;y++) if(g[x][y]){
			for(int z=2;x*z<=100;z++){
				for(int b=y;b<x*z;b+=x) g[x*z][b]=1,vis[x*z][b]=1;
			}
		}
	}
	for(int x=100;x;x--){
		for(int y=0;y<x;y++)if(!g[x][y]){
			for(int z=2;x*z<=100;z++){
				int flag=0;
				for(int b=y;b<x*z;b+=x) if(!g[x*z][b]) flag=1;
				if(!flag){
					g[x][y]=1;
					for(int b=y;b<x*z;b+=x) vis[x*z][b]=1;
				}
			}
		}
	}
	
	const int I=64*81*25*49;
	bitset<I+5> f;
	for(int x=1;x<=100;x++) if(I%x==0) for(int y=0;y<x;y++) if(g[x][y]){
		for(int z=y;z<I;z+=x) f[z]=1;
	}
	for(int x=1;x<=100;x++) if(I%x==0) for(int y=0;y<x;y++) if(!g[x][y]){
		int flag=0;
		for(int z=y;z<I;z+=x) if(!f[z]){flag=1;break;}
		if(!flag) g[x][y]=1;
	}
	initprim();
	for(int x=1;x<=100;x++){
		for(int y=0;y<x;y++) if(g[x][y]){
			for(int z=2;x*z<=100;z++){
				for(int b=y;b<x*z;b+=x) g[x*z][b]=1,vis[x*z][b]=1;
			}
		}
	}
	for(int x=100;x;x--){
		for(int y=0;y<x;y++)if(!g[x][y]){
			for(int z=2;x*z<=100;z++){
				int flag=0;
				for(int b=y;b<x*z;b+=x) if(!g[x*z][b]) flag=1;
				if(!flag){
					g[x][y]=1;
					for(int b=y;b<x*z;b+=x) vis[x*z][b]=1;
				}
			}
		}
	}
	for(int x=100;x;x--){
		for(int y=0;y<x;y++) if(!vis[x][y]&&g[x][y]){gdb(x);BigInt::mul(x);break;}
	}
	BigInt::print();
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}