#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 SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

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

using namespace std;

const int maxn = 5010;
const int I = 2520;

int sid, n, m, dfn[maxn], low[maxn], col[maxn], ins[maxn], stk[maxn], top, tot, timer;
int g[maxn], len[maxn], vis[maxn], nop[110], used[110], mx[110];
bitset<110> g1[maxn][110], g2[maxn][110], f[110], relf[110], And[110];
vector<pii> e[maxn], gr[maxn];

void tarjan(int u) {
  dfn[u] = low[u] = ++timer, ins[u] = 1, stk[++top] = u;
  for (auto [v, w] : e[u]) {
    if (!dfn[v]) tarjan(v), chkmn(low[u], low[v]);
    else if (ins[v]) chkmn(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    col[u] = ++tot;
    while (stk[top] != u) col[stk[top]] = tot, ins[stk[top--]] = 0;
    top--, ins[u] = 0;
  }
}

void getg(int u) {
  vis[u] = 1, ins[u] = 1;
  for (auto [v, w] : gr[u]) {
    if (!vis[v]) {
      len[v] = len[u] + w, getg(v);
    } else if (ins[v]) {
      g[col[u]] = gcd(g[col[u]], len[u] - len[v] + w);
    } else {
      g[col[u]] = gcd(g[col[u]], abs(len[v] - len[u] - w));
    }
  }
  ins[u] = 0;
}

void dfs(int u, int t, int mod) {
  if (g1[u][mod].test(t)) return;
  g1[u][mod].set(t);
  for (auto [v, w] : e[u]) dfs(v, (t + w) % mod, mod);
}

void dfs2(int u, int t, int mod) {
  if (g2[u][mod].test(t)) return;
  g2[u][mod].set(t);
  for (auto [v, w] : e[u]) dfs2(v, (t + w) % mod, mod);
}

void add(int x) {
  rep (i, 2, 100) if (x % i == 0) {
    int cnt = 0;
    while (x % i == 0) cnt++, x /= i;
    chkmx(mx[i], cnt);
  }
}

int get(int p) {
  rep (d, 1, p) if (p % d == 0) {
    int ok = 1;
    rep (m, 0, d - 1) {
      rep (k, 0, p / d - 1) ok &= (f[p][m] == f[p][m + k * d]);
    }
    if (ok) return d;
  }
  return p;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m >> sid;
  rep (i, 2, 100) if (!nop[i]) {
    rep (j, 2, 100 / i) nop[i * j] = 1;
  }
  rep (i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    e[u].emplace_back(v, w);
  }
  tarjan(1);
  if (!dfn[n]) return cout << "1\n", 0;
  rep (u, 1, n) for (auto [v, w] : e[u]) {
    if (col[u] == col[v]) gr[u].emplace_back(v, w);
  }
  rep (i, 1, n) vis[i] = ins[i] = 0;
  rep (i, 1, n) if (!vis[i]) getg(i);
  rep (d, 1, 100) dfs(1, 0, d);
  rep (i, 1, n) if (g[col[i]]) {
    rep (j, 0, g[col[i]] - 1) if (g1[i][g[col[i]]].test(j)) dfs2(i, j, g[col[i]]);
  }
  rep (d, 1, 100) f[d] = g2[n][d];
  rep (d, 1, 100) rep (j, 0, d - 1) f[d].flip(j);
  rep (p, 0, 2519) {
    rep (d, 1, 100) {
      And[d].reset();
      rep (i, 0, d - 1) And[d].set(i);
    }
    rep (d, 1, 100) {
      int w = gcd(d, I), mod = d / w;
      bitset<110> cur;
      for (int i = p % w; i < d; i += w) {
        if (f[d].test(i)) cur.set(i % mod);
      }
      And[mod] &= cur;
    }
    rep (d, 2, 100) if (!nop[d]) {
      int val = d;
      while (val * d <= 100) {
        bitset<110> cur;
        rep (g, 0, d - 1) cur |= (And[val] << (val * g));
        val *= d, And[val] &= cur;
      }
      while (val != d) {
        bitset<110> cur;
        rep (g, 0, d - 1) cur |= (And[val] >> ((val / d) * g));
        val /= d, And[val] &= cur;
      }
    }
    int ok = 1;
    rep (d, 1, 100) if (!And[d].count()) ok = 0;
    if (!ok) continue;
    rep (d, 1, 100) {
      int w = gcd(d, I), mod = d / w;
      for (int i = p % w; i < d; i += w) {
        if (And[mod].test(i % mod)) relf[d].set(i);
      }
    }
  }
  rep (d, 1, 100) f[d] &= relf[d];
  if (!f[1].test(0)) return cout << "1\n", 0;
  rep (d, 1, 50) {
    rep (p, 2, 100 / d) {
      bitset<110> cur;
      rep (w, 0, p - 1) cur |= (f[d] << (w * d));
      f[d * p] &= cur;
    }
  }
  rep (d, 51, 100) add(get(d));
  int ans = 1;
  rep (i, 1, 100) rep (j, 1, mx[i]) ans = 1ll * ans * i % 1000000009;
  cout << ans << '\n';
}