#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000009
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
int n,m,C,type;
vector <pii> G[2][5005],GG[5005];

int dfn[5005],low[5005],tag[5005],fr[5005],N,scc;
vector <int> sta;
void tarjan(int u){
	dfn[u] = low[u] = ++N;
	tag[u] = 1;
	sta.eb(u);
	for(pii vv:G[0][u]){
		int v = vv.first;
		if(!dfn[v]){
			tarjan(v);
			chkmin(low[u],low[v]);
		}else if(tag[v]){
			chkmin(low[u],dfn[v]);
		}
	}
	if(low[u] < dfn[u]) return;

	++scc;
	while(1){
		int p = sta.back();
		sta.pop_back();
		tag[p] = 0;
		fr[p] = scc;
		if(p == u) break;
	}
}

int a[5005],cir[5005];
void dfs(int u){
	for(pii vv:GG[u]){
		int v = vv.first;
		if(a[v] == -1){
			a[v] = a[u] + vv.second;
			dfs(v);
		}else{
			cir[fr[u]] = __gcd(cir[fr[u]],abs(a[v] - a[u] - vv.second));
		}
	}
}

int op,mmod;
int dp[2][5005][105];
queue <pii> Q;
void psh(int u,int val){
	if(dp[op][u][val]) return;
	dp[op][u][val] = 1;
	Q.push(mkp(u,val));
}

void ssolver(){
//	printf("ssolver\n");
	while(!Q.empty()){
		pii cur = Q.front();
		Q.pop();
		for(pii v:G[op][cur.first]) psh(v.first,(cur.second + v.second) % mmod);
	}
//	printf("fin\n");
}

int valid[105][105],ss[1008005];
bitset <1008005> _valid[105];
void solver(){
	rep(u,1,n){
		fill(dp[0][u],dp[0][u] + mmod,0);
		fill(dp[1][u],dp[1][u] + mmod,0);
	}
	op = 0;
	psh(1,0);
	ssolver();

	op = 1;
	psh(n,0);
	ssolver();

	rep(u,1,n){
		if(cir[fr[u]] != mmod) continue;
		rep(i,0,mmod - 1){
			rep(j,0,mmod - 1) if(dp[0][u][i] && dp[1][u][j]) valid[mmod][(i + j) % mmod] = 1;
		}
	}
/*	printf("mmod=%d\n",mmod);
	rep(i,0,mmod - 1) printf("%d ",valid[mmod][i]);
	printf("\n");*/
}
int fail[1008005];
int getminperiod(int *f,int len){
	int j = 0;
	rep(i,2,len){
		while(j && f[j + 1] != f[i]) j = fail[j];
		if(f[j + 1] == f[i]) j++;
		fail[i] = j;		
	}
	while(j && len % (len - j)) j = fail[j];
	return len - j;
}

int rk[105];
void bouns(int val){
	rep(i,2,C){
		if(val % i) continue;
		int temp = 0;
		while(val % i == 0){
			val /= i;
			temp++;
		}
		chkmax(rk[i],temp);
	}
}

int sqr(int x){
	return x * x;
}
int pcnt;
int _tag[105],pri[105],bel[105],exs[105],M;
void sieve(){
	rep(i,2,C){
		if(!_tag[i]) pri[++pcnt] = i;
		for(int j = 1;j <= pcnt && i * pri[j] <= C;j++){
			_tag[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
	pri[pcnt + 1] = C + 1;
	exs[1] = bel[1] = 1;
	M = 1;
	rep(i,1,pcnt){
		int cur = 1,need = 1;
		while(need * pri[i] * pri[i + 1] <= C) need *= pri[i];
		while(cur * pri[i] <= C) cur *= pri[i];
		int Mx = cur / need;
		cur = 1;
		while(cur <= need){
			bel[cur] = 1;
			cur *= pri[i];
		}
		while(cur <= C){
			bel[cur] = Mx;
			cur *= pri[i];
		}
		exs[Mx] = 1;
		M *= need;
//		if(need > 1) printf("%d->%d\n",pri[i],need);
	}
/*	printf("M=%d\n",M);
	rep(i,1,pcnt) printf("%d ",pri[i]);
	printf("\n");
	rep(i,1,C) printf("%d ",bel[i]);
	printf("\n");
	rep(i,1,C) if(exs[i]) printf("important %d\n",i);*/
}

int eval(int cur){
	int qwq = M,ret = 1,k;
	rep(i,1,pcnt){
		k = 0;
		while(cur % pri[i] == 0){
			cur /= pri[i];
			k++;
		}
		if(!k) continue;
		rep(s,1,k - 1) if(qwq % pri[i] == 0) qwq /= pri[i];
		if(qwq % pri[i]) while(k--) ret *= pri[i];
	}
	return ret;
}

int main(){
//	freopen("loop55.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d%d",&n,&m,&type);
	rep(i,1,m){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		G[0][u].eb(v,w);G[1][v].eb(u,w);
	}
	rep(u,1,n) if(!dfn[u]) tarjan(u);
//	rep(u,1,n) printf("%d ",fr[u]);
//	printf("\n");
	rep(u,1,n){
		for(pii vv:G[0][u]) if(fr[u] == fr[vv.first]) GG[u].eb(vv);
	}
	fill(a,a + n + 1,-1);
	rep(u,1,n){
		if(a[u] != -1) continue;
		a[u] = 0;
		dfs(u);
	}
//	rep(i,1,scc) printf("%d ",cir[i]);
//	printf("\n");
	rep(i,1,scc) chkmax(C,cir[i]);
	assert(C <= 100);
	if(!C){
		printf("1\n");
		return 0;
	}
//	printf("C=%d\n",C);

	sieve();
	rep(i,1,C){
		mmod = i;
		solver();
		int idx = bel[eval(i)];
		assert(idx && idx * M % i == 0);
		int mul = idx * M / i,pos = 0;
//		printf("%d idx %d mul %d\n",i,idx,mul);
		rep(pp,0,mul - 1){
			rep(j,0,i - 1){
				if(valid[i][j]) _valid[idx].set(pos);
				pos++;
			}
		}
//		rep(j,0,i - 1) printf("%d ",valid[i][j]);
//		printf("\n");
	}
	rep(p,0,M - 1){
		int pure = 0,sp;
		rep(i,1,C){
			if(!exs[i]) continue;
			sp = 1;
			for(int j = 0,k = p;j < i;j++,k += M){
				if(!_valid[i].test(k)){
					sp = 0;
					break; 
				}
			}
			pure |= sp;
		}		
		if(pure){
			rep(i,1,C){
				if(!exs[i]) continue;
				for(int j = 0,k = p;j < i;j++,k += M) _valid[i].set(k);
			}
		}
	}
	
	rep(i,1,C){
		if(!exs[i]) continue;
		rep(k,1,i * M) ss[k] = _valid[i][k - 1];
/*		rep(k,1,i * M){
			printf("%d",ss[k]);
			if(k % M == 0) printf("\n");
		}
		printf("\n\n");*/
		bouns(getminperiod(ss,i * M));		
	}

	Z result = 1;
	rep(i,1,C){
		while(rk[i]){
			result *= i;
			rk[i]--;
		}
	}
	printf("%d\n",result.val());
	return 0;
}