func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 2e3 + 10;   const int mod = 1e9 + 7;   int read() {     int x = 0, f = 1;     char c = getchar();     while (c <  0  || c >  9 ) {       if (c ==  - ) f = -1;       c = getchar();     }     while (c >=  0  && c <=  9 ) x = (x << 1) + (x << 3) + c -  0 , c = getchar();     return x * f;   }   int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }   int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }   int qpow(int a, int x, int mo) {     int res = 1;     while (x) {       if (x & 1) res = 1ll * res * a % mo;       a = 1ll * a * a % mod;       x >>= 1;     }     return res;   }   vector<pair<int, int> > g[N];   long long dp[N][N];   map<int, long long> mp;   int q[N];   int main() {     int n = read(), m = read(), Q = read();     for (int i = 0; i < m; i++) {       int u = read(), v = read(), w = read();       g[u].push_back(make_pair(v, w));       g[v].push_back(make_pair(u, w));     }     for (int i = 0; i <= m; i++)       for (int j = 1; j <= n; j++) dp[i][j] = -2e18;     dp[0][1] = 0;     int ans = 0;     for (int i = 1; i <= m; i++) {       long long res = 0;       for (int j = 1; j <= n; j++)         for (int t = 0; t < g[j].size(); t++) {           pair<int, int> now = g[j][t];           int u = now.first, v = j;           dp[i][u] = max(dp[i - 1][v] + now.second, dp[i][u]);           if (i == m)             mp[now.second] = max(dp[i - 1][v] + now.second, mp[now.second]);           res = max(res, dp[i][u]);         }       ans = inc(ans, res % mod);     }     vector<pair<int, int> > p;     for (auto it : mp) {       p.push_back(it);     }     int head = 1, tail = 0;     int Inv2 = qpow(2, mod - 2, mod);     for (int i = 0; i < p.size(); i++) {       while (head <= tail && p[q[tail]].second <= p[i].second) tail--;       q[++tail] = i;     }     Q -= m;     int cnt = 0;     int pre = 1;     for (int i = 2; i <= tail; i++) {       pair<int, int> now = p[q[pre]];       pair<int, int> nxt = p[q[i]];       bool ok = 1;       long long k = (now.second - nxt.second) / (nxt.first - now.first);       for (int j = i + 1; j <= tail; j++) {         pair<int, int> o = p[q[j]];         if ((now.second - o.second) / (o.first - now.first) <= k) {           ok = 0;           break;         }       }       k -= cnt;       if (k <= 0 || ok == 0) continue;       if (Q <= k) k = Q;       ans = inc(ans, inc(1ll * k * (1 + k) % mod * Inv2 % mod * now.first % mod,                          1ll * (now.second + 1ll * cnt * now.first % mod) % mod *                              k % mod));       Q -= k;       cnt += k;       pre = i;       if (Q == 0) break;     }     pair<int, int> now = p[q[tail]];     if (Q > 0)       ans = inc(ans, inc(1ll * Q * (1 + Q) % mod * Inv2 % mod * now.first % mod,                          1ll * (now.second + 1ll * cnt * now.first % mod) % mod *                              Q % mod));     printf( %d n , ans);   }   