#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=5e3+10,M=102,k=100,P=2520,mod=1e9+9;
int n,m,s,t,sid,a[N];
vector<pair<int,int>>to[N];
int dft,sct,dfn[N],low[N],scc[N];
void tarjan(int u){
	static int top,stk[N];
	dfn[u]=low[u]=++dft,stk[++top]=u;
	for(auto [v,w]:to[u]){
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		sct++;
		do scc[stk[top]]=sct;while(stk[top--]^u);
	}
}
bitset<N>f[M][N];
vector<pair<int,int>>tr[N];
int vis[N][M];
bitset<M>g[N][M],h[M],ok[M];
int val[M],w[M][M],inv[M][M];
void dfs1(int p,int u,int x){
	if(vis[u][x])return;
	// debug("dfs1",p,u,x);
	vis[u][x]=1;
	for(auto [v,w]:tr[u]){
		if(!a[scc[v]])dfs1(p,v,(x+w)%p);
	}
}
void dfs2(int u,int p,int x){
	p=w[p][a[scc[u]]],x%=p;
	if(g[u][p][x])return;
	// debug("dfs2",u,p,x);
	g[u][p][x]=1;
	for(auto [v,w]:to[u])dfs2(v,p,x+w);
}
int main(){
	for(int i=0;i<=k;i++){
		val[i]=__gcd(P,i);
		for(int j=0;j<=k;j++)w[i][j]=__gcd(i,j);
		for(int x=1;x<i;x++)for(int y=1;y<i;y++){
			if(x*y%i==1)inv[i][x]=y;
		}
	}
	cin>>n>>m>>sid,s=1,t=n;
	vector<tuple<int,int,int>>E(m);
	for(auto &[u,v,w]:E){
		cin>>u>>v>>w;
		if(!w)to[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(auto &[u,v,w]:E)u=scc[u],v=scc[v];
	for(int u=1;u<=n;u++)to[u].clear();
	s=scc[s],t=scc[t];
	fill(dfn,dfn+1+n,0),fill(scc,scc+1+n,0),n=sct,dft=sct=0;
	for(auto [u,v,w]:E)if(w||u!=v)to[u].push_back({v,w});
	// debug("s t",s,t);
	// for(auto [u,v,w]:E)debug(u,v,w);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int u=1;u<=n;u++)f[0][u][u]=1;
	for(int i=1;i<=k;i++){
		for(int u=1;u<=n;u++){
			for(auto [v,w]:to[u])if(w<=i){
				f[i][u]|=f[i-w][v];
			}
		}
		for(int u=1;u<=n;u++)if(f[i][u][u]){
			a[scc[u]]=__gcd(a[scc[u]],i);
		}
	}
	for(int u=1;u<=n;u++){
		for(auto [v,w]:to[u]){
			tr[v].push_back({u,w});
		}
	}
	for(int u=1;u<=n;u++)if(a[scc[u]]){
		dfs1(a[scc[u]],u,0);
		for(int i=0;i<a[scc[u]];i++)if(vis[s][i])dfs2(u,0,i);
		memset(vis,0,sizeof vis);
	}
	// for(int p=1;p<=k;p++){
	// 	for(int x=0;x<p;x++){
	// 		if(g[t][p][x])debug("equiv",x,"(mod",p,")");
	// 	}
	// }
	for(int p=1;p<=k;p++)g[t][p].flip();
	for(int b=0;b<P;b++){
		static bitset<P>is;
		is.set();
		for(int p=1;p<=k;p++)if(val[p]==1)h[p].set();
		for(int p=1;p<=k;p++){
			int gcd=val[p],mod=p/gcd;
			static bitset<M>cur;
			cur.reset();
			for(int x=0;x<p;x++)if(g[t][p][x]){
				if((x-b)%gcd==0){
					cur[((x-b)/gcd%mod+mod)*inv[mod][P/gcd%mod]%mod]=1;
				}
			}
			if(val[mod]>1){
				for(int i=0;i<mod;i++)if(!cur[i]){
					for(int j=i;j<P;j+=mod)is[j]=0;
				}
			}else h[mod]&=cur;
		}
		[&](){
			if(!is.count())return;
			for(int p=1;p<=k;p++){
				if(val[p]==1&&!h[p].count())return;
			}
			for(int p=1;p<=k;p++){
				int gcd=val[p],mod=p/gcd;
				for(int x=0;x<p;x++)if(g[t][p][x]){
					if((x-b)%gcd==0){
						int r=((x-b)/gcd%mod+mod)*inv[mod][P/gcd%mod]%mod;
						if(val[mod]>1){
							for(int i=r;i<P&&!ok[p][x];i+=mod){
								if(is[i])ok[p][x]=1;
							}
						}else if(h[mod][r])ok[p][x]=1;
					}
				}
			}
		}();
	}
	for(int p=1;p<=k;p++){
		for(int x=0;x<p;x++)if(g[t][p][x]){
			if(!ok[p][x])g[t][p][x]=0;
		}
	}
	// for(int p=1;p<=k;p++){
	// 	for(int x=0;x<p;x++){
	// 		if(g[t][p][x])debug("new equiv",x,"(mod",p,")");
	// 	}
	// }
	static int res[M];
	auto insert=[&](int x){
		for(int i=2;i<=k;i++){
			int cnt=0;
			for(;x%i==0;x/=i)cnt++;
			res[i]=max(res[i],cnt);
		}
	};
	for(int p=1;p<=k;p++){
		static int c[M],nex[M];
		for(int x=0;x<p;x++)c[x+1]=g[t][p][x];
		for(int i=2,j=0;i<=p;i++){
			for(;j&&c[j+1]!=c[i];j=nex[j]);
			nex[i]=j+=c[j+1]==c[i];
		}
		int len=p-nex[p];
		if(p%len)len=p;
		insert(len);
	}
	int ans=1;
	for(int i=1;i<=k;i++){
		for(int t=res[i];t--;)ans=1ll*ans*i%mod;
	}
	cout<<ans<<endl;
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif