#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 5050
#define M 10010
#define K 105
#define mod 1000000009
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

const int B=100;
int n,m;
struct Edge{int u,v,w;}e[M];
std::vector<std::pair<int,int>>G[N];

IL void add(reg int u,reg int v,reg int w)
{
    G[u].push_back({v,w});
}

int gcd(reg int x,reg int y){return y?gcd(y,x%y):x;}

int dfn[N],low[N],s[N],top,dfc;
bool in[N];

IL void cmin(reg int &x,reg int y){x>y?x=y:0;}

int blo[N],scc,w[N];

void tarjan(reg int u)
{
    dfn[u]=low[u]=++dfc,in[s[++top]=u]=1;
    for(auto &[v,w]:G[u])
        if(!dfn[v])tarjan(v),cmin(low[u],low[v]);
        else if(in[v])cmin(low[u],dfn[v]);
    if(dfn[u]==low[u])
    {
        ++scc;
        do in[s[top]]=0,blo[s[top]]=scc; while(s[top--]!=u);
    }
}

bool vis[N];
int dep[N],P;

IL int Abs(reg int x){return x<0?-x:x;}

void dfs(reg int u)
{
    vis[u]=1;
    for(auto &[v,w]:G[u])
        if(!vis[v])dep[v]=dep[u]+w,dfs(v);
        else P=gcd(P,Abs(dep[u]+w-dep[v]));
}

const int T=2520;
bool f1[N][K][K],f2[N][K][K],g[K][K],h[K][K];
int col[K],inv[K][K],a[K],tot;
int cnt[K][K];

main()
{
    n=read(),m=read(),read();
    for(reg int i=1;i<=m;++i)e[i]={read(),read(),read()},add(e[i].u,e[i].v,e[i].w);
    for(reg int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
    for(reg int i=1,j,rt;i<=scc;++i)
    {
        for(j=1;j<=n;++j)G[j].clear();
        P=0;
        for(j=1;j<=m;++j)if(blo[e[j].u]==i&&blo[e[j].v]==i)
            add(e[j].u,e[j].v,e[j].w);
        for(j=1;j<=n;++j)if(blo[j]==i)rt=j;
        dfs(rt),w[i]=P;
    }
    for(reg int i=1;i<=n;++i)G[i].clear();
    for(reg int i=1;i<=m;++i)add(e[i].u,e[i].v,e[i].w);
    std::queue<std::tuple<int,int,int>>q1,q2;

    auto add1=[&](reg int u,reg int p,reg int r) -> void
    {
        if(!f1[u][p][r])f1[u][p][r]=1,q1.push({u,p,r});
    };

    auto add2=[&](reg int u,reg int p,reg int r) -> void
    {
        if(!f2[u][p][r])f2[u][p][r]=1,q2.push({u,p,r});
    };

    for(reg int i=1;i<=B;++i)add1(1,i,0);
    while(!q1.empty()||!q2.empty())
    {
        if(!q1.empty())
        {
            auto [u,p,r]=q1.front(); q1.pop();
            if(p==w[blo[u]])add2(u,p,r);
            for(auto &[v,w]:G[u])add1(v,p,(w+r)%p);
        }
        if(!q2.empty())
        {
            auto [u,p,r]=q2.front(); q2.pop();
            add2(u,gcd(p,w[blo[u]]),r%gcd(p,w[blo[u]]));
            for(auto &[v,w]:G[u])add2(v,p,(w+r)%p);
        }
    }
    for(reg int i=1,j;i<=B;++i)for(j=0;j<i;++j)g[i][j]=!f2[n][i][j];
    for(reg int i=2,j,k;i<=B;++i)
    {
        bool isp=1;
        for(j=2;j<i;++j)if(i%j==0)isp=0;
        if(!isp)continue;
        for(k=i;k<=B;k*=i);
        for(j=i;j<=B;j*=i)col[j]=k/i;
    }
    col[1]=1;
    for(reg int p=1,q,t;p<=B;++p)for(q=1;q<p;++q)if(gcd(p,q)==1)
    {
        for(t=0;t*q%p!=1;++t);
        inv[p][q]=t;
    }
    for(reg int r=0,i,j,k,d,p;r<T;++r)
    {
        static bool vis[K];
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=B;++i)
        {
            d=gcd(i,T),p=i/d,memset(vis,0,sizeof(vis));
            for(j=0;j<i;++j)if(g[i][j]&&j%d==r%d)
                vis[((j-r)/d*inv[p][T/d%p]%p+p)%p]=1;
            for(j=0;j<col[p];++j)cnt[col[p]][j]+=!vis[j%p];
        }

        bool ok=1;
        for(i=1;i<=B;++i)if(col[i]==i)
        {
            bool find=0;
            for(j=0;j<i;++j)find|=!cnt[i][j];
            ok&=find;
        }
        if(!ok)continue;
        for(i=1;i<=B;++i)
        {
            d=gcd(i,T),p=i/d,memset(vis,0,sizeof(vis));
            for(j=0;j<i;++j)if(g[i][j]&&j%d==r%d)
                vis[((j-r)/d*inv[p][T/d%p]%p+p)%p]=1;
            for(j=0;j<col[p];++j)cnt[col[p]][j]+=vis[j%p];
            static bool ok[K];
            for(j=0;j<p;++j)
            {
                ok[j]=0;
                for(k=j;k<col[p];k+=p)ok[j]|=!--cnt[col[p]][k];
                for(k=j;k<col[p];k+=p)++cnt[col[p]][k];
            }
            for(j=0;j<i;++j)if(g[i][j]&&j%d==r%d)
                h[i][j]|=ok[((j-r)/d*inv[p][T/d%p]%p+p)%p];
            for(j=0;j<col[p];++j)cnt[col[p]][j]-=vis[j%p];
        }
    }

    for(reg int i=1,j,d;i<=B;++i)
    {
        bool all0=1;
        for(j=0;j<i;++j)all0&=!h[i][j];
        if(all0)puts("1"),exit(0);
        for(d=1;d<=i;++d)if(i%d==0)
        {
            bool ok=1;
            for(j=d;j<i;++j)ok&=h[i][j]==h[i][j-d];
            if(ok)
            {
                a[++tot]=d;
                break;
            }
        }
    }
    for(reg int i=2,j;i<=tot;++i)for(j=1;j<i;++j)a[i]/=gcd(a[i],a[j]);
    reg int ans=1;
    for(reg int i=1;i<=tot;++i)ans=1ll*ans*a[i]%mod;
    printf("%d\n",ans);
}