#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const long long inf = 5e18;
const int N = 2e3 + 100;
vector<pair<int, int> > g[N];
long long dist[N];
pair<long long, long long> get_max(vector<pair<long long, long long> > cand,
                                   long long cnt) {
  long long mx = 0, mxidx = -1;
  for (int i = 0; i < cand.size(); i++) {
    long long du = cand[i].first, w = cand[i].second;
    if (du + w * cnt > mx) {
      mx = du + w * cnt;
      mxidx = i;
    }
  }
  return {mx, mxidx};
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dist[1] = 0;
  for (int i = 2; i <= n; i++) dist[i] = LLONG_MIN;
  long long ans = 0;
  for (int ctr = 0; ctr < m; ctr++) {
    long long upd[n + 1];
    for (int u = 1; u <= n; u++) upd[u] = LLONG_MIN;
    for (int u = 1; u <= n; u++) {
      for (auto x : g[u]) {
        int v = x.first, w = x.second;
        upd[v] = max(upd[v], dist[u] + w);
      }
    }
    long long mx = 0;
    for (int u = 1; u <= n; u++) {
      dist[u] = max(dist[u], upd[u]);
      mx = max(mx, dist[u]);
    }
    ans = (ans + mx) % mod;
  }
  q -= m;
  vector<pair<long long, long long> > cand;
  for (int u = 1; u <= n; u++) {
    int mw = 0;
    if (dist[u] < 0) continue;
    for (auto x : g[u]) {
      int w = x.second;
      mw = max(w, mw);
    }
    cand.push_back({dist[u], mw});
  };
  int cn = cand.size();
  while (q > 0) {
    pair<long long, long long> mx = get_max(cand, 1);
    int mxidx = mx.second;
    long long lo = 1, hi = q, mid, bans = q + 1;
    while (lo <= hi) {
      mid = (lo + hi) >> 1;
      pair<long long, long long> curr = get_max(cand, mid);
      int curridx = curr.second;
      if (curridx != mxidx) {
        bans = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    bans--;
    long long dmxidx = cand[mxidx].first, wmxidx = cand[mxidx].second;
    ;
    ans += ((dmxidx % mod) * bans) % mod;
    long long bsq = (bans * (bans + 1)) / 2;
    bsq %= mod;
    ans += (wmxidx * bsq) % mod;
    ans %= mod;
    for (int i = 0; i < cn; i++) {
      long long w = cand[i].second;
      cand[i].first += (w * bans);
    }
    q -= bans;
  }
  cout << (ans + mod) % mod << endl;
}
