#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll MOD = 1LL << 32;
ll add(ll x, ll y) {
    x += y;
    if (x >= MOD) return x - MOD;
    return x;
}
ll mult(ll x, ll y) {
    return (x * y) % MOD;
}

struct Item {
    int w;
    int id, pos;

    Item() : w(), id(), pos() {}
    Item(int _w, int _id, int _pos) : w(_w), id(_id), pos(_pos) {}

    bool operator < (const Item &I) const {
        if (w != I.w) return w < I.w;
        if (id != I.id) return id < I.id;
        return pos < I.pos;
    }
};

const int N = 1010;
map<Item, int> a;
vector<int> g[N];
int ed[2 * N][3];
int n, m;
vector<int> b[N];
int k;
ll ans;
int par[N];
int h[N];
int sumAll = 0;

int getOther(int id, int v) {
    return ed[id][0] ^ ed[id][1] ^ v;
}

void dfs(int v) {
    for (int id : g[v]) {
        int u = getOther(id, v);
        if (par[u] == -1) {
            par[u] = id;
            h[u] = h[v] + 1;
            dfs(u);
        } else if (h[u] < h[v] - 1) {
            b[m].push_back(ed[id][2]);
            int w = v;
            while(w != u) {
                b[m].push_back(ed[par[w]][2]);
                w = getOther(par[w], w);
            }
            m++;
        }
    }
}

int main()
{
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &ed[i][0], &ed[i][1], &ed[i][2]);
        ed[i][0]--;
        ed[i][1]--;
        g[ed[i][0]].push_back(i);
        g[ed[i][1]].push_back(i);
        sumAll += ed[i][2];
    }
    scanf("%d", &k);
    m = 0;
    for (int i = 0; i < n; i++)
        par[i] = -1;
    par[0] = -2;
    dfs(0);
    for (int id = 0; id < m; id++) {
        sort(b[id].begin(), b[id].end());
        reverse(b[id].begin(), b[id].end());
        sumAll -= b[id][0];
        for (int i = 0; i < (int)b[id].size() - 1; i++)
            b[id][i] = b[id][i] - b[id][i + 1];
        b[id].pop_back();
    }
    sort(b, b + m);
    a[Item(sumAll, 0, 0)] = 1;
    ll curNum = 1;
    while(!a.empty() && k > 0) {
        Item v = a.begin()->first;
        int cnt = a.begin()->second;
        a.erase(a.begin());
        for (int i = 0; i < cnt && k > 0; i++) {
            ans = add(ans, mult(curNum, v.w));
            curNum++;
            k--;
        }
        if (k == 0) break;
        if ((int)b[v.id].size() > v.pos) {
            Item I = v;
            I.w += b[v.id][v.pos];
            I.pos++;
            a[I] = min(a[I] + cnt, k);
        }
        if (v.id != 0 && v.id < m - 1 && v.pos == 1) {
            Item I = v;
            I.id++;
            I.w += b[I.id][0] - b[v.id][0];
            a[I] = min(a[I] + cnt, k);
        }
        if (v.id < m - 1) {
            Item I = v;
            I.id++;
            I.pos = 1;
            I.w += b[I.id][0];
            a[I] = min(a[I] + cnt, k);
        }
    }
    printf("%lld\n", ans);

    return 0;
}