#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const long long M = (long long)1e9 + 7;
void check(long long a) {}
long long add(long long a, long long b) {
  a %= M;
  b %= M;
  a += b;
  if (a >= M) return a - M;
  if (a < 0) return a + M;
  return a;
}
long long mul(long long a, long long b) {
  a %= M;
  b %= M;
  check(a);
  check(b);
  return a * (long long)b % M;
}
long long pw(long long a, long long b) {
  a %= M;
  check(a);
  long long r = 1;
  while (b) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}
long long dv(long long a, long long b) {
  check(a);
  check(b);
  return mul(a, pw(b, M - 2));
}
const long long N = 2000 + 7;
const long long OO = (long long)1e18 + 7;
long long n, m, q, top;
long long summax[N][N];
vector<pair<long long, long long>> e[N];
struct T {
  long long a, b;
};
long long eval(T it, long long x) { return it.a * x + it.b; }
T ln[N];
bool operator<(T f, T s) {
  if (f.a == s.a) {
    return f.b > s.b;
  } else {
    return f.a < s.a;
  }
}
long double isect(T f, T s) {
  long double a1 = f.a, b1 = f.b;
  long double a2 = s.a, b2 = s.b;
  return (b2 - b1) / (a1 - a2);
}
long long gauss(long long p) {
  long long sol = mul(p % M, p + 1);
  sol = dv(sol, 2);
  return sol;
}
long long gauss(long long l, long long r) {
  return add(gauss(r), -gauss(l - 1));
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  bool oke;
  cin >> n >> m >> q;
  oke = (n == 2000 && m == 1999 && q == 20001);
  for (long long i = 1; i <= m; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    e[a].push_back({b, c});
    e[b].push_back({a, c});
  }
  for (long long i = 0; i < N; i++)
    for (long long j = 0; j < N; j++) summax[i][j] = -OO;
  summax[0][1] = 0;
  for (long long ced = 0; ced < m; ced++) {
    for (long long i = 1; i <= n; i++) {
      for (auto &it : e[i]) {
        long long j = it.first;
        long long val = summax[ced][i] + it.second;
        summax[ced + 1][j] = max(summax[ced + 1][j], val);
      }
    }
  }
  long long sol = 0;
  for (long long ed = 1; ed <= min(q, m); ed++) {
    long long best = 0;
    for (long long i = 1; i <= n; i++) {
      best = max(best, summax[ed][i]);
    }
    sol = add(sol, best % M);
  }
  for (long long i = 1; i <= n; i++) {
    long long bigBrother = 0;
    for (auto &it : e[i]) {
      bigBrother = max(bigBrother, it.second);
    }
    ln[i] = {bigBrother, summax[m][i] - bigBrother * (long long)m};
  }
  if (q < m + 1) {
    cout << sol << "\n";
    return 0;
  }
  long long l = m + 1, r = q;
  sort(ln + 1, ln + n + 1);
  top = 0;
  for (long long i = 1; i <= n; i++) {
    if (top == 0 || ln[i].a != ln[i - 1].a) {
      ln[++top] = ln[i];
    }
  }
  n = top;
  top = 0;
  for (long long i = 1; i <= n; i++) {
    while (top >= 2 &&
           isect(ln[top - 1], ln[i]) < isect(ln[top - 1], ln[top])) {
      top--;
    }
    ln[++top] = ln[i];
  }
  n = top;
  top = 0;
  long long first = l;
  for (long long i = 1; i <= n; i++) {
    long long last = r;
    if (i < n) {
      last = isect(ln[i], ln[i + 1]);
      if (last < first) {
        continue;
      }
    }
    if (last > r) {
      last = r;
    }
    long long a = ln[i].a % M;
    long long b = ln[i].b % M;
    if (a < 0) a += M;
    if (b < 0) b += M;
    sol = add(sol, mul(last - first + 1, b));
    sol = add(sol, mul(a, gauss(first, last)));
    first = last + 1;
  }
  cout << sol << "\n";
  return 0;
}
