#include<iostream>
#include<cstdio>
#include<vector>
#define N 5000
#define M 100
#define K 2520
#define mod 1000000009
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int gcd(int x,int y)
{
	if (!y) return x;
	return gcd(y,x%y);
}
void Adder(int &x,int d)
{
	x=x+d>=mod?x+d-mod:x+d;
	return;
}
struct reads
{
	int num,data;
};
int n,m,type,ans=1,dres,tans,dque[N+1],tops,slen[M+1],num[M+1],maxn[M+1],tong[M+1],length,belong[N+1],cater,delta[M+1],dfn[N+1],low[N+1],leng,st[M+1],st2[M+1],stk[N+1],top,cnt[M+1][K+1];
long long depth[N+1];
vector<reads>E[N+1];
vector<reads>E2[N+1];
vector<reads>ES[N+1];
vector<int>v[N+1];
bool used[N+1],dp[N+1][M+1],dp2[N+1][M+1],vis[M+1][M+1],nprime[M+1];
void tarjan(int x)
{
	dfn[x]=low[x]=++leng,used[x]=1,stk[++top]=x;
	for (int i=0;i<E[x].size();++i)
	{
		if (!dfn[E[x][i].num]) tarjan(E[x][i].num),low[x]=min(low[x],low[E[x][i].num]);
		else if (used[E[x][i].num]) low[x]=min(low[x],dfn[E[x][i].num]);
	}
	if (dfn[x]==low[x])
	{
		++cater;
		while (stk[top]!=x) belong[stk[top]]=cater,used[stk[top]]=0,top--;
		belong[stk[top]]=cater,used[stk[top]]=0,top--;
	}
	return;
}
void dfs(int x)
{
	used[x]=1,dque[++tops]=x;
	for (int i=0;i<ES[x].size();++i)
	{
		if (!used[ES[x][i].num]) depth[ES[x][i].num]=depth[x]+ES[x][i].data,dfs(ES[x][i].num);
		else dres=gcd(dres,abs(depth[ES[x][i].num]-depth[x]-ES[x][i].data));
	}
	return;
}
void dfs2(int x,int d)
{
	dp[x][d]=1;
	for (int i=0;i<E[x].size();++i)
		if (!dp[E[x][i].num][(d+E[x][i].data)%dres])
			dfs2(E[x][i].num,(d+E[x][i].data)%dres);
	return;
}
void dfs3(int x,int d)
{
	dp2[x][d]=1;
	for (int i=0;i<E2[x].size();++i)
		if (!dp2[E2[x][i].num][(d+E2[x][i].data)%dres])
			dfs3(E2[x][i].num,(d+E2[x][i].data)%dres);
	return;
}
int A[N+1],W[N+1];
bool check(int x,int sp)
{
	int y,d,rst=2520,len,res=1,tres=0;
	bool op;
	while (rst%sp==0) rst/=sp;
	rst*=min(2520/rst,x);
	for (int i=0;i<rst;++i)
	{
		for (int j=1;j<=length;++j)
			for (int k=0;k<st[j];++k)
				cnt[j][k]=0;
		for (int j=1;j<=100;++j)
		{
			y=j;
			while (y%sp==0) y/=sp;
			y=y*min(j/y,x),d=gcd(y,rst),len=tong[num[y]]==sp?x:st[num[y]];
			for (int k=0;k<len;++k) cnt[num[y]][k]++;
			for (int k=i%d;k<y;k+=d)
			{
				op=1;
				for (int t=k;t<j;t+=y) op&=vis[j][t];
				if (op)
				{
					for (int t=k%slen[y];t<len;t+=slen[y]) cnt[num[y]][t]--;
				}
			}
		}
		res=1;
		for (int j=1;j<=length;++j)
		{
			delta[j]=0,len=tong[j]==sp?x:st[j];
			for (int k=0;k<len;++k) delta[j]+=(!cnt[j][k]);
			res=1ll*res*delta[j]%mod;
		}
		W[i]=res,Adder(tres,res);
	}
	for (int i=1;i<=length;++i)
		if (tong[i]==sp)
			tres=1ll*tres*(st2[i]/x)%mod*(st2[i]/x)%mod;
	return tres==tans;
}
int main()
{
	int x,y,z,d,scnt,res;
	bool opt;
	for (int i=2;i<=100;++i)
		if (!nprime[i])
		{
			tong[++length]=i,scnt=0;
			for (int j=i;j<=100;j*=i) ++scnt,st[length]=j;
			st2[length]=maxn[length]=1;
			for (int j=1;j<=(scnt>>1);++j) st2[length]*=i;
			for (int j=st2[length]*i;j<=100;j+=st2[length]*i) num[j]=length;
			for (int j=(i<<1);j<=100;j+=i) nprime[j]=1;
		}
	tong[++length]=1,st[length]=st2[length]=maxn[length]=1;
	for (int i=1;i<=100;++i)
		if (!num[i])
			num[i]=length;
	for (int i=1;i<=100;++i)
	{
		if (tong[num[i]]==1) slen[i]=1;
		else
		{
			d=i,slen[i]=1;
			while (d%tong[num[i]]==0) d/=tong[num[i]],slen[i]*=tong[num[i]];
		}
	}
	n=read(),m=read(),type=read();
	for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),E[x].push_back((reads){y,z}),E2[y].push_back((reads){x,z});
	for (int i=1;i<=n;++i)
		if (!dfn[i])
			tarjan(i);
	for (int i=1;i<=n;++i)
		for (int j=0;j<E[i].size();++j)
			if (belong[i]==belong[E[i][j].num])
				ES[i].push_back(E[i][j]),ES[E[i][j].num].push_back((reads){i,-E[i][j].data});
	for (int i=1;i<=n;++i)
		if (!used[i])
		{
			tops=dres=0,dfs(i);
			if (dres)
			{
				for (int j=1;j<=tops;++j) v[dres].push_back(dque[j]);
			}
		}
	for (int i=1;i<=100;++i)
	{
		dres=i;
		for (int j=1;j<=n;++j)
			for (int k=0;k<dres;++k)
				dp[j][k]=dp2[j][k]=0;
		dfs2(1,0),dfs3(n,0);
		for (int j=0;j<v[i].size();++j)
			for (int k=0;k<dres;++k)
				for (int t=0;t<dres;++t)
					if (dp[v[i][j]][k]&&dp2[v[i][j]][t])
						vis[dres][(k+t)%dres]=1;
	}
	for (int i=1;i<=100;++i)
		for (int j=0;j<i;++j)
			vis[i][j]=!vis[i][j];
	for (int i=0;i<2520;++i)
	{
		for (int j=1;j<=length;++j)
			for (int k=0;k<st[j];++k)
				cnt[j][k]=0;
		for (int j=1;j<=100;++j)
		{
			d=gcd(j,2520);
			for (int k=0;k<st[num[j]];++k) cnt[num[j]][k]++;
			for (int k=i%d;k<j;k+=d)
				if (vis[j][k])
				{
					for (int t=k%slen[j];t<st[num[j]];t+=slen[j]) cnt[num[j]][t]--;
				}
		}
		res=1;
		for (int j=1;j<=length;++j)
		{
			delta[j]=0;
			for (int k=0;k<st[j];++k) delta[j]+=(!cnt[j][k]);
			res=1ll*res*delta[j]%mod;
		}
		Adder(tans,res),A[i]=res;
		if (res)
		{
			for (int j=1;j<=length;++j)
			{
				for (int k=1;k<st[j];k*=tong[j])
					if (k>=st2[j])
					{
						opt=1;
						for (int t=0;t<st[j];++t) opt&=((!cnt[j][t])==(!cnt[j][t%k]));
						if (!opt) maxn[j]=max(maxn[j],k*tong[j]);
					}
			}
		}
	}
	for (int i=1;i<=4;++i)
		if (maxn[i]==1)
		{
			for (int j=1;j<st2[i];j*=tong[i])
				if (!check(j,tong[i]))
					maxn[i]=max(maxn[i],j*tong[i]);
		}
	for (int i=1;i<=length;++i) ans=1ll*ans*maxn[i]%mod;
	printf("%d\n",ans);
	return 0;
}