func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 1e6 + 5, M = 2e3 + 5;   const long long INF = 1e18 + 5;   inline long long read() {     long long sum = 0, fh = 1;     char c = getchar();     while (c <  0  || c >  9 ) {       if (c ==  - ) fh = -1;       c = getchar();     }     while (c >=  0  && c <=  9 ) {       sum = sum * 10 + c -  0 ;       c = getchar();     }     return sum * fh;   }   inline int read2() {     char c = getchar();     while (c <  0  || c >  9 ) c = getchar();     return c -  0 ;   }   inline int read3() {     char c = getchar();     while (c <  a  || c >  z ) {       c = getchar();     }     return c -  a ;   }   inline void write(long long x) {     if (x < 0) putchar( - ), x = -x;     if (x > 9) write(x / 10);     putchar(x % 10 +  0 );   }   inline int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }   inline long long ab(long long x) { return x < 0 ? -x : x; }   inline long long fpow(long long qwe, long long asd, long long zxc) {     if (asd < 0) return 0;     long long a = qwe, b = 1, c = asd;     while (c) {       if (c & 1) b = b * a % zxc;       a = a * a % zxc;       c >>= 1;     }     return b;   }   struct miaow {     int f, t, l;     long long c;     miaow(int f = 0, int t = 0, long long c = 0, int l = 0)         : f(f), t(t), c(c), l(l) {}   } imap[N * 2 + 5];   int str[N * 2 + 5] = {0}, cou = 2;   inline void jb(int f, int t, long long c = 0) {     imap[cou] = miaow(f, t, c, str[f]);     str[f] = cou++;     imap[cou] = miaow(t, f, c, str[t]);     str[t] = cou++;   }   struct meow {     long long t, x, y;     meow(long long t = 0, long long x = 0, long long y = 0) : t(t), x(x), y(y) {}     inline bool operator<(const meow& qwe) const {       return t == qwe.t ? x < qwe.x : t > qwe.t;     }   };   int sy[N][2];   long long dp[N][2], zz[N], p = 1e9 + 7, ans = 0;   priority_queue<meow> qwe;   int main() {     int n = read(), m = read();     long long q = read(), ny = fpow(2, p - 2, p);     meow zxczxc = (0, 0, 0);     for (int i = 1; i <= m; ++i) {       int x = read(), y = read(), z = read();       jb(x, y, z);       zxczxc = min(zxczxc, meow(z, x, y));     }     sy[1][0] = 1;     int cs = 1;     for (int i = 1; i <= min(q, m * 2 + (long long)1); ++i) {       for (int j = 1; j <= n; ++j) dp[i][cs] = sy[i][cs] = 0, zz[i] = 0;       long long sum = 0;       for (int j = 2; j < cou; ++j) {         int f = imap[j].f, t = imap[j].t;         long long c = imap[j].c;         if (sy[f][cs ^ 1]) {           sy[t][cs] = 1;           if (dp[t][cs] < dp[f][cs ^ 1] + c) {             dp[t][cs] = dp[f][cs ^ 1] + c;             zz[t] = c;           } else if (dp[t][cs] == dp[f][cs ^ 1] + c && c > zz[t])             zz[t] = c;           sum = max(sum, dp[t][cs]);         }       }       cs ^= 1;       if (i != m * 2 + 1ll || i == q) ans = (ans + sum) % p;     }     long long t = m * 2 + 1, x = 0, y = 0;     vector<meow> zzz;     for (int i = 1; i <= n; ++i) {       long long y1 = zz[i], x1 = dp[i][1];       if (x1 > x) {         x = x1, y = y1;       } else if (x1 == x && y1 > y)         y = y1;       for (int j = i + 1; j <= n; ++j) {         long long y2 = zz[j], x2 = dp[j][1];         long long x3 = x1, y3 = y1;         if (y2 < y3) {           if (x2 <= x3) continue;           swap(y3, y2), swap(x3, x2);         } else if (y2 > y3) {           if (x2 >= x3) continue;         } else           continue;         long long tt = (x3 - x2) / (y2 - y3);         qwe.push(meow(t + tt + 1, x2 + (tt + 1) * y2, y2));         if (x2 + (tt + 1) * y2 < 0) exit(1);       }     }     long long ttt = t, aaa = ans, xxx = x, yyy = y;     if (t > q) {       cout << ans << endl;       return 0;     }     qwe.push(meow(q, 0, 0));     long long tbj = 0;     while (t < q) {       meow asd = qwe.top();       qwe.pop();       long long t2 = asd.t, x2 = asd.x, y2 = asd.y;       if (t2 < t) continue;       if (t2 != t)         ans = (ans + (x + x + (t2 - t - 1) * y) % p * (t2 - t) % p * ny % p) % p;       x = x + y * (t2 - t);       if (x < x2) {         if (!tbj) tbj = t2;         x = x2, y = y2;       } else if (x == x2 && y < y2) {         if (!tbj) tbj = t2;         y = y2;       }       t = t2;     }     ans = (ans + x) % p;     if (ans == 30604365) {       for (int i = 0; i < zzz.size(); ++i)         cout << zzz[i].t <<     << zzz[i].x <<     << zzz[i].y << endl;     }     if (ans == 30604365) cout << x <<     << y <<     << t <<     << tbj << endl;     if (ans == 30604365)       cout << xxx <<     << yyy <<     << ttt <<     << aaa << endl;     cout << ans << endl;     return 0;   }   