#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U>
using Pa = pair<T, U>;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
constexpr ll mod = 1e9 + 7;
struct mint {
  ll x;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  friend ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
  friend istream& operator>>(istream& is, mint& a) {
    ll t;
    is >> t;
    a = mint(t);
    return (is);
  }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
};
ll inf = -1e18;
template <typename T>
class MonotoneCHT {
 public:
  struct line {
    T a, b;
    line(T a, T b) : a(a), b(b) {}
    bool operator<(const line& r) const {
      return (a != r.a ? a < r.a : b < r.b);
    }
    bool operator>(const line& r) const {
      return (a != r.a ? a > r.a : b > r.b);
    }
  };
  int h = 0;
  vector<line> lines;
  bool isMonotonicX;
  function<bool(T l, T r)> comp;
  MonotoneCHT(bool flagX, function<bool(T l, T r)> compFunc)
      : isMonotonicX(flagX), comp(compFunc) {}
  bool check(line l1, line l2, line l3) {
    if (l1 < l3) swap(l1, l3);
    return (long double)(l3.b - l2.b) * (l2.a - l1.a) <=
           (long double)(l2.b - l1.b) * (l3.a - l2.a);
  }
  void add(T a, T b) {
    line l(a, b);
    while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), l))
      lines.pop_back();
    lines.emplace_back(l);
  }
  T f(int i, T x) { return lines[i].a * x + lines[i].b; }
  T f(line l, T x) { return l.a * x + l.b; }
  T get(T x) {
    if (isMonotonicX) {
      static int head = 0;
      while (lines.size() - head >= 2 && comp(f(head, x), f(head + 1, x)))
        head++;
      h = head;
      return f(head, x);
    } else {
      int l = -1, r = lines.size() - 1;
      while (l + 1 < r) {
        int m = (l + r) / 2;
        (comp(f(m, x), f(m + 1, x)) ? l : r) = m;
      }
      return f(r, x);
    }
  }
  T getnow(T x) { return f(h, x); }
  T getnext(T x) {
    if (h + 1 == lines.size())
      return inf;
    else
      return f(h + 1, x);
  }
  T geta() { return lines[h].a; }
  T getb() { return lines[h].b; }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M, Q;
  cin >> N >> M >> Q;
  struct edge {
    int to;
    ll d;
  };
  vvec<edge> g(N);
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  vvec<ll> dp(M + 1, vec<ll>(N + 1, inf));
  dp[0][0] = 0;
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++)
      if (dp[i][j] != inf) {
        for (auto& e : g[j]) {
          dp[i + 1][e.to] = max(dp[i + 1][e.to], dp[i][j] + e.d);
        }
      }
  }
  mint ans = 0;
  for (int i = 1; i <= M; i++) ans += *max_element(dp[i].begin(), dp[i].end());
  map<ll, ll> mp;
  for (int i = 0; i <= M; i++) {
    for (int j = 0; j < N; j++) {
      for (auto& e : g[j]) {
        if (!mp.count(e.d))
          mp[e.d] = -e.d * i + dp[i][j];
        else if (mp[e.d] < -e.d * i + dp[i][j]) {
          mp[e.d] = -e.d * i + dp[i][j];
        }
      }
    }
  }
  MonotoneCHT<ll> cht(true, [](ll a, ll b) { return a <= b; });
  for (auto x : mp) cht.add(x.first, x.second);
  ll now = M + 1;
  auto sum = [&](ll x) { return x * (x + 1) / 2; };
  while (now <= Q) {
    ll l = now, r = Q + 1;
    ll val = cht.get(now);
    while (l + 1 < r) {
      ll m = (l + r) / 2;
      if (cht.getnow(m) < cht.getnext(m))
        r = m;
      else
        l = m;
    }
    ll a = cht.geta(), b = cht.getb();
    mint k = sum(r - 1);
    k -= sum(now - 1);
    ans += k * a + (r - now) * b;
    now = r;
  }
  cout << ans << "\n";
}
