#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vpii = vector<pii>;
const int N = 2050;
const int MOD = 1e9 + 7;
ll dist[N];
ll dist2[N];
struct edge {
  ll w, b, a, b2;
  ll l, r;
  int was;
} e[N];
vector<edge> a;
bool operator<(const edge &a, const edge &b) {
  return a.w > b.w || (a.w == b.w && a.b > b.b);
}
vpii g[N];
int n, m, q;
ll lider;
ll ans[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 0; i < m; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    g[x].push_back({y, i});
    g[y].push_back({x, i});
    e[i].w = z;
    e[i].a = i;
  }
  fill(dist, dist + n + 1, -1LL);
  dist[1] = 0;
  for (int t = 1; t <= n; ++t) {
    fill(dist2, dist2 + n + 1, -1LL);
    lider = -1;
    for (int i = 1; i <= n; ++i)
      if (dist[i] >= 0)
        for (auto p : g[i]) {
          ll tmp = dist[i] + e[p.second].w;
          if (dist2[p.first] < tmp) {
            dist2[p.first] = tmp;
            lider = max(lider, tmp);
          }
          tmp = dist[i] - (t - 1) * e[p.second].w;
          if (!e[p.second].was || e[p.second].b < tmp) {
            e[p.second].was = 1;
            e[p.second].b = tmp;
          }
        }
    for (int i = 1; i <= n; ++i) {
      dist[i] = dist2[i];
    }
    ans[t] = lider;
  }
  if (q <= n) {
    cout << accumulate(ans + 1, ans + 1 + q, 0LL) % MOD << "\n";
    return 0;
  }
  sort(e, e + m);
  for (auto &ee : e) {
    ll tmp = MOD;
    while (tmp + ee.b < 0) tmp *= 10;
    ee.b2 = (ee.b + tmp) % MOD;
  }
  e[0].l = n + 1;
  e[0].r = q;
  a.push_back(e[0]);
  for (int i = 1; i < m; ++i) {
    if (e[i].w == e[i - 1].w) continue;
    vector<edge> an;
    int maxj = -1;
    ll maxn = -1;
    for (int j = 0; j < a.size(); ++j) {
      auto &ee = a[j];
      if ((e[i].b - ee.b) < 0) continue;
      ll p = e[i].b - ee.b;
      ll q = ee.w - e[i].w;
      ll nn = p / q;
      if (q * nn >= p) nn--;
      if (nn < ee.l) break;
      maxj = j;
      maxn = min(nn, ee.r);
    }
    if (maxj == -1) continue;
    if (maxn == a[maxj].r) {
      e[i].l = n + 1;
      e[i].r = maxn;
      a[maxj] = e[i];
      a.erase(a.begin(), a.begin() + maxj);
    } else {
      a.erase(a.begin(), a.begin() + maxj);
      a[0].l = maxn + 1;
      e[i].l = n + 1;
      e[i].r = maxn;
      a.insert(a.begin(), e[i]);
    }
  }
  lider = accumulate(ans + 1, ans + 1 + n, 0LL) % MOD;
  for (auto &e : a) {
    ll tmp = (e.l + e.r) * (e.r - e.l + 1) / 2 % MOD;
    tmp = tmp * e.w + e.b2 * (e.r - e.l + 1);
    lider = (lider + tmp) % MOD;
  }
  cout << lider << "\n";
  return 0;
}
