#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define FastI
#define FastO
//#define int ll
bool ST;
static const ll MOD=1e9+9,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
int x,y,z;
tup(int X=0,int Y=0,int Z=0)
{x=X,y=Y,z=Z;}
inline bool operator <(const tup t)const
{return x<t.x||(x==t.x&&y<t.y)
||(x==t.x&&y==t.y&&z<t.z);}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
template<typename T> inline void write(T x,char ch=' ')
{
if(is_same<char,T>::value)putchar(x);
else
{
if(x<0)x=-x,putchar('-');
static char st[40];
int top=0;
do st[top++]=x%10+'0',x/=10;while(x);
while(top)putchar(st[--top]);
}
ch!='~'?putchar(ch):0;
}
inline void write(const char*x,char ch=' ')
{
for(int i=0;x[i]!='\0';++i)putchar(x[i]);
ch!='~'?putchar(ch):0;
}
inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
inline void read(char s[])
{
int len=0;char st;
do st=getchar();while(st=='\n'||st==' ');
s[++len]=st,st=getchar();
while(st!='\n'&&st!=' '&&st!='\r'&&st!='\0')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
char ch=getchar();s=0;
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
bool tf=(ch=='-'&&(ch=getchar()));
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
s=tf?-s:s;
}
inline void edl(){putchar('\n');}
template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
#ifdef FastO
struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
#endif
}
using namespace FastIO;
namespace MTool
{
inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
inline int sqr(int a){return 1ll*a*a%MOD;}
inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
int n,m,C;
bitset<110> f[5010][110],g[5010][110],h[110],vis,can[110];
tup a[10010];
vp G[5010];
int d[5010];
int tot,dfn[5010],low[5010];
int num,c[5010],sum[5010];
int ins[5010];
vi ve[5010];
stack<int> st;
void tarjan(int x)
{
st.e(x),ins[x]=1,dfn[x]=low[x]=++tot;
for(auto [to,v]:G[x])
{
if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]);
else if(ins[to])low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x])
{
int y;++num;
do
{
y=st.top(),st.pop();
c[y]=num,ins[y]=0;
ve[num].eb(y);
}while(y!=x);
}
}
inline int Gcd(int x,int y){return !x||!y?(x^y):__gcd(x,y);}
inline int calc(int x,int y)
{
int s=0;
while(x%y==0)++s,x/=y;
return s;
}
int tmp=0;
void dfs(int x)
{
for(auto [to,v]:G[x])if(c[to]==c[x])
{
if(d[to]==-1)d[to]=d[x]+v,dfs(to);
else tmp=Gcd(tmp,abs(d[x]-d[to]+v));
}
}
void upd(int x,int y,int z)
{
if(f[x][y][z])return;
f[x][y][z]=1;
if(sum[x]!=0)return;
for(auto [to,v]:G[x])upd(to,y,(z+v)%y);
}
void upd2(int x,int y,int z)
{
if(g[x][y][z])return;
g[x][y][z]=1;
for(auto [to,v]:G[x])
{
int V=Gcd(y,sum[to]);
upd2(to,V,(z+v)%V);
}
}
int nex[110];
int get(int id)
{
for(int i=2,j=0;i<=id;++i)
{
while(j&&h[id][j+1]!=h[id][i])j=nex[j];
if(h[id][j+1]==h[id][i])++j;
nex[i]=j;
}
if(id%(id-nex[id])==0)return id-nex[id];
return id;
}
const int B=2520;
bitset<110> use[110],real[110];
void mian()
{
read(n,m,C);
int x,y,z;
for(int i=1;i<=m;++i)
{
read(x,y,z),a[i]=tup(x,y,z);
G[x].eb(mp(y,z));
}
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
memset(d,-1,sizeof(d));
for(int i=1;i<=num;++i)
{
tmp=0;
d[ve[i][0]]=0;
dfs(ve[i][0]);
for(auto p:ve[i])sum[p]=tmp;
}
for(int i=1;i<=100;++i)upd(1,i,0);
for(int i=1;i<=n;++i)if(sum[i])
{
for(int k=0;k<sum[i];++k)if(f[i][sum[i]][k])
upd2(i,sum[i],k);
}
for(int i=1;i<=100;++i)h[i]=~(g[n][i]<<1);
for(int r=0;r<B;++r)
{
for(int i=1;i<=100;++i)for(int j=0;j<i;++j)use[i][j]=1;
for(int i=1;i<=100;++i)
{
int d=i/Gcd(i,B);
for(int j=0;j<d;++j)
use[d][j]=use[d][j]&h[i][(j*B+r)%i+1];
}
int flag=1;
for(int i=1;i<=100;++i)
{
for(int j=i+i;j<=100;j+=i)
{
for(int k=0;k<j;++k)
use[j][k]=use[j][k]&use[i][k%i];
}
int fl=0;
for(int j=0;j<i;++j)fl|=use[i][j];
if(!fl){flag=0;break;}
}
if(flag)for(int i=1;i<=100;++i)real[r%i]=1;
}
for(int i=1;i<=100;++i)
{
int d=i/Gcd(i,B);
for(int j=0;j<100;++j)if(real[i][j])
{
for(int k=0;k<d;++k)
can[i][(k*B+r)%i+1]=1;
}
}
for(int i=1;i<=100;++i)h[i]&=can[i];
// for(int i=1;i<=100;++i,cerr<<endl)for(int j=1;j<=i;++j)
// cerr<<h[i][j];
for(int i=1;i<=100;++i)
{
for(int j=i+i;j<=100;j+=i)
{
for(int k=1;k<=j;++k)
h[j][k]=h[j][k]&h[i][(k-1)%i+1];
}
}
vi ans;
for(int i=100;i>=1;--i)
{
int tmp=get(i);
if(tmp==i)ans.eb(i);
else h[tmp]&=h[i];
}
if(h[1][1]==0)return puts("1");
int Ans=1;
for(int i=2;i<=100;++i)if(!vis[i])
{
int v=0;
for(auto p:ans)Mmax(v,calc(p,i));
Mmul(Ans,power(i,v));
for(int j=i+i;j<=100;j+=i)vis[j]=1;
}
write(Ans,'~');
}
inline void Mian()
{
int T=1;
// read(T);
while(T--)mian();
}
}
bool ED;
signed main()
{
// ios::sync_with_stdio(0);
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
double st=clock();
WrongAnswer_90::Mian();
double ed=clock();
cerr<<endl;
cerr<<"Time: "<<ed-st<<" ms\n";
cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
return 0;
}