func_code_string: #include <bits/stdc++.h>   using namespace std;   int64_t dp[2004], nx[2004];   struct pt {     int64_t v, c;   };   int main() {     ios::sync_with_stdio(false);     int n, m, q;     cin >> n >> m >> q;     vector<vector<pair<int, int>>> G(n + 1);     vector<int> val(n + 1, 0);     vector<int64_t> cost(n + 1, 0);     for (int i = 0; i < m; ++i) {       int a, b, c;       cin >> a >> b >> c;       G[a].push_back({b, c});       G[b].push_back({a, c});       val[a] = max(val[a], c);       val[b] = max(val[b], c);     }     int64_t ans = 0, md = 1000000007;     for (int j = 2; j <= n; ++j) dp[j] = -1e12;     for (int i = 0; i < m; ++i) {       int64_t tm = 0;       for (int j = 1; j <= n; ++j) {         nx[j] = -1e12;         for (auto to : G[j]) {           nx[j] = max(nx[j], dp[to.first] + to.second);         }         tm = max(tm, nx[j]);       }       ans = (ans + tm) % md;       swap(dp, nx);     }     for (int i = 1; i <= n; ++i) {       cost[i] = val[i] * 1ll * m - dp[i];     }     vector<pt> v;     for (int i = 1; i <= n; ++i) {       v.push_back({val[i], cost[i]});     }     int64_t nowq = m + 1;     int64_t mx = 0;     int mxi = 0;     for (int i = 0; i < v.size(); ++i) {       if (nowq * v[i].v - v[i].c > mx) {         mx = nowq * v[i].v - v[i].c;         mxi = i;       }     }     while (nowq <= q) {       int64_t nxq = q + 1;       for (int i = 0; i < v.size(); ++i) {         if (v[i].v > v[mxi].v) {           nxq = min(nxq, 1 + (v[i].c - v[mxi].c) / (v[i].v - v[mxi].v));         }       }       int64_t q2 = (nxq - nowq) * (nxq - nowq - 1) / 2;       q2 %= md;       ans += (nxq - nowq) * (mx % md) + (v[mxi].v * q2) % md;       ans %= md;       mx = 0;       for (int i = 0; i < v.size(); ++i) {         if (nxq * v[i].v - v[i].c > mx) {           mx = nxq * v[i].v - v[i].c;           mxi = i;         }       }       nowq = nxq;     }     cout << ans << endl;   }   