#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5;
const int Mod=1000000009;

int x[N], y[N], z[N];
int head[N], nex[N], to[N], len[N], col[N], indx, ans;
bool vis[N];

void add_edge(int x,int y,int z)
{
	indx++;
	nex[indx]=head[x];
	to[indx]=y;
	len[indx]=z;
	head[x]=indx;
}

void dfs(int x)
{
	vis[x]=true;
	for(int i=head[x];i;i=nex[i])
	{
		int y=to[i];
		if(!vis[y])
		{
			col[y]=(col[x]+len[i])%ans;
			dfs(y);
		}
	}
}

int low[N], dfsn[N], bel[N], root[N], SCC, cnt;
bool instack[N];
vector <int> point[N];
stack <int> s;

void tarjan(int x)
{
	low[x]=dfsn[x]=++cnt;
	s.push(x);
	instack[x]=true;
	for(int i=head[x];i;i=nex[i])
	{
		int y=to[i];
		if(!dfsn[y])
			tarjan(y),low[x]=min(low[x],low[y]);
		else if(instack[y])
			low[x]=min(low[x],dfsn[y]);
	}

	if(low[x]==dfsn[x])
	{
		SCC++;
		root[SCC]=x;
		int y=0;
		do
		{
			y=s.top();
			s.pop();
			bel[y]=SCC;
			point[SCC].push_back(y);
			instack[y]=false;
		}
		while(y!=x);
	}
}

int val[N], ind[N], Max[105];
bool have[5005][105][105], have0[5005][105][105], can[205][205];
queue <int> q;

int gcd(int x,int y)
{
	if(x>y)
		swap(x,y);

	if(x==0)
		return y;

	return gcd(y%x,x);
}

int lcm(int x,int y)
{
	if(!x && !y)
		return 0;

	if(!x)
		return y;

	if(!y)
		return x;

	return x*y/gcd(x,y);
}

long long qsm(int x,int y)
{
	if(!y)
		return 1;

	long long t=qsm(x,y/2);
	if(y%2==0)
		return t*t%Mod;
	return t*t%Mod*x%Mod;
}

int main()
{
	int n,m,type;
	cin >> n >> m >> type;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x[i],&y[i],&z[i]);
		add_edge(x[i],y[i],z[i]);
	}

	for(int i=1;i<=n;i++)
		if(!dfsn[i])
			tarjan(i);

	memset(head,0,sizeof(head));
	memset(nex,0,sizeof(nex));
	memset(to,0,sizeof(to));
	memset(len,0,sizeof(len));
	indx=0;
	for(int i=1;i<=m;i++)
		if(bel[x[i]]==bel[y[i]])
			add_edge(x[i],y[i],z[i]);

	for(int i=1;i<=SCC;i++)
	{
		bool allzero=true;
		for(auto x:point[i])
			for(int j=head[x];j;j=nex[j])
				if(len[j]!=0)
					allzero=false;

		if(allzero)
		{
			val[i]=0;
			continue;
		}

		for(ans=100;ans>=1;ans--)
		{
			for(auto x:point[i])
				vis[x]=col[x]=0;

			dfs(root[i]);

			bool good=true;
			for(auto x:point[i])
				for(int j=head[x];j;j=nex[j])
					if(col[to[j]]!=(col[x]+len[j])%ans)
						good=false;

			if(good)
			{
				val[i]=ans;
				break;
			}
		}
	}

	memset(head,0,sizeof(head));
	memset(nex,0,sizeof(nex));
	memset(to,0,sizeof(to));
	memset(len,0,sizeof(len));
	indx=0;
	int s=bel[1], t=bel[n];
	for(int i=1;i<=m;i++)
		if(bel[x[i]]!=bel[y[i]])
		{
			add_edge(bel[x[i]],bel[y[i]],col[x[i]]+z[i]+val[bel[y[i]]]-col[y[i]]);
			ind[bel[y[i]]]++;
		}

	if(val[s]==0)
	{
		for(int GCD=1;GCD<=100;GCD++)
			have0[s][GCD][0]=true;
	}
	else
		have[s][val[s]][0]=true;

	for(int i=1;i<=SCC;i++)
		if(ind[i]==0)
			q.push(i);

	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int j=head[x];j;j=nex[j])
		{
			int y=to[j], z=len[j];
			for(int GCD=1;GCD<=100;GCD++)
			{
				int newGCD=gcd(GCD,val[y]);
				for(int len=0;len<GCD;len++)
					if(have[x][GCD][len])
						have[y][newGCD][(z+len)%newGCD]=true;
			}

			if(val[y]==0)
			{
				for(int GCD=1;GCD<=100;GCD++)
					for(int len=0;len<GCD;len++)
						if(have0[x][GCD][len])
							have0[y][GCD][(len+z)%GCD]=true;
			}
			else
			{
				for(int len=0;len<val[y];len++)
					if(have0[x][val[y]][len])
						have[y][val[y]][(z+len)%val[y]]=true;
			}

			ind[y]--;
			if(ind[y]==0)
				q.push(y);
		}
	}

	for(int i=1;i<=100;i++)
		for(int j=0;j<i;j++)
			can[i][j]=have[t][i][j];

	for(int cnt=1;cnt<=100;cnt++)
	{
		for(int i=1;i<=200;i++)
			for(int k=0;k<i;k++)
				if(can[i][k])
					for(int j=2;i*j<=200;j++)
						for(int p=0;p<i*j;p++)
							if(p%i==k)
								can[i*j][p]=true;

		for(int i=200;i>=1;i--)
		{
			for(int k=1;k<=i;k++)
			{
				bool good=true;
				for(int j=0;j<i;j++)
					if(can[i][j]!=can[i][(j+k)%i])
						good=false;

				if(good)
				{
					val[i]=k;
					break;
				}
			}

			for(int k=1;k<i;k++)
			{
				if(i%k!=0)
					continue;

				for(int j=0;j<k;j++)
				{
					bool allone=true;
					for(int p=j;p<i;p+=k)
						if(!can[i][p])
							allone=false;

					if(allone)
						can[k][j]=true;
				}
			}
		}
	}

	for(int i=1;i<=200;i++)
		for(int j=2;j<=200;j++)
		{
			int q=0;
			while(val[i]%j==0)
			{
				val[i] /= j;
				q++;
			}

			Max[j]=max(Max[j],q);
		}

	long long ans=1;
	for(int i=1;i<=100;i++)
		(ans *= qsm(i,Max[i])) %= Mod;
	printf("%lld\n",ans);
	return 0;
}