/*

HDU 6041 - I Curse Myself [ 图论,找环,最大k和 ]  |  2017 Multi-University Training Contest 1

题意：

	给出一个仙人掌图，求最小的k棵生成树

	N <= 1000, M <= 2000, K <= 1e5

分析：

	将问题转化为从每个环中选出一条边，求最大的k个和

	首先找环，随便怎么找，比如 在保证每条边只走一次的情况下遍历到祖先节点就说明有环，记录一下前驱就能找出来

	然后是每个环两两合并，此时相当于两个vector，res.size() = k，cir[i].size() = Mi, ∑mi = M

	由于 M<=2000,k <= 1e5，故选择在堆中的元素是cir[i]中的元素

	这样就能保证复杂度为 O( ∑K*log(mi) ) = O( K*log(∏mi) ) <= O(K*M)

编码时长: INF(-8)

*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const LL MOD = 1LL<<32;

const int N = 1005;

struct Edge {

    int to, next, w;

    bool vis;

}edge[N<<2];

int head[N], tot;

void init() {

    memset(head, -1, sizeof(head));

    tot = 0;

}

void addedge(int u, int v, int w) {

    edge[tot].to = v; edge[tot].next = head[u];

    edge[tot].vis = 0; edge[tot].w = w;

    head[u] = tot++;

}

int n, m, block;

vector<int> cir[N];

bool vis[N];

int f[N], g[N];//父节点和连着的边

void dfs(int u)

{

    for (int i = head[u]; i != -1; i = edge[i].next)

    {

        int v = edge[i].to;

        if (edge[i].vis) continue;

        edge[i].vis = 1;

        edge[i^1].vis = 1;

        if (vis[v])

        {

            ++block;

            int t = u;

            do{

                cir[block].push_back(edge[g[t]].w);

                t = f[t];

            }while (t != v);

            cir[block].push_back(edge[i].w);

        }

        else

        {

            vis[v] = 1, f[v] = u, g[v] = i;

            dfs(v);

        }

    }

}

void find_cir()

{

    for (int i = 0; i < N; i++) cir[i].clear();

    memset(vis, 0, sizeof(vis));

    block = 0;

    vis[1] = 1;

    dfs(1);

}

struct Node {

    int x, id;

    bool operator < (const Node& b) const {//大的先出去

        return x < b.x;

    }

};

priority_queue<Node> Q;

vector<int> res, tmp;

void solve(int k)

{

    res.clear();

    res.push_back(0);

    for (int i = 1; i <= block; ++i)

    {

        while (!Q.empty()) Q.pop();

        tmp.clear();

        for (auto& x : cir[i])

            Q.push(Node{x+res[0], 0});

        while (tmp.size() < k && !Q.empty())

        {

            auto p = Q.top(); Q.pop();

            tmp.push_back(p.x);

            if (p.id+1 < res.size())

            {

                ++p.id;

                p.x += res[p.id] - res[p.id-1];

                Q.push(p);

            }

        }

        res.clear();

        for (auto& x : tmp) res.push_back(x);

    }

}

int main()

{

    int tt = 0, u, v, w, k;

    while (~scanf("%d%d", &n, &m))

    {

        init();

        LL sum = 0, ans = 0;

        for (int i = 1; i <= m; i++)

        {

            scanf("%d%d%d", &u, &v, &w);

            sum += w;

            addedge(u, v, w); addedge(v, u, w);

        }

        find_cir();

        scanf("%d", &k);

        solve(k);

        for (int i = 0; i < res.size(); i++)

            ans += (i+1) * ( (sum-res[i])) % MOD;

        printf("Case #%d: %lld\n", ++tt, ans%MOD);

    }

}

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 1005;

const LL MOD = 1LL<<32;

struct Edge {

    int to, next, w;

    bool vis;

}edge[N<<2];

int head[N], tot;

void init() {

    memset(head, -1, sizeof(head));

    tot = 0;

}

void addedge(int u, int v, int w) {

    edge[tot].w = w; edge[tot].to = v; edge[tot].next = head[u];

    edge[tot].vis = 0;

    head[u] = tot++;

}

int block;

vector<int> cir[N];

int f[N], g[N], vis[N];

void dfs(int u)

{

    for (int i = head[u]; ~i; i = edge[i].next)

    {

        if (edge[i].vis) continue;

        edge[i].vis = 1;

        edge[i^1].vis = 1;

        int v = edge[i].to;

        if (vis[v])

        {

            ++block;

            int t = u;

            do {

                cir[block].push_back(edge[g[t]].w);

                t = f[t];

            }while (t != v);

            cir[block].push_back(edge[i].w);

        }

        else

        {

            vis[v] = 1;

            f[v] = u, g[v] = i;

            dfs(v);

        }

    }

}

void find_cir()

{

    for (int i = 0; i < N; i++) cir[i].clear();

    memset(vis, 0, sizeof(vis));

    block = 0;

    vis[1] = 1;

    dfs(1);

}

bool cmp (const int &x, const int &y) {

    return x > y;

}

int n, m, k, num;

LL mid, res[100005];

void dfs(int i, LL sum)

{

    if (num > k) return;

    if (sum > mid) return;

    if (i == block+1)

    {

        res[++num] = sum; return;

    }

    for (auto& x : cir[i])

    {

        if (sum + x > mid) break;

        dfs(i+1, sum+x);

    }

}

LL BinaryFind(LL l, LL r)

{

    while (l <= r)

    {

        mid = (l+r)>>1;

        num = 0;

        dfs(1, 0);

        if (num >= k) r = mid-1;

        else l = mid+1;

    }

    return l;

}

int main()

{

    int t = 0, x, y, z;

    while (~scanf("%d%d", &n, &m))

    {

        init();

        LL base = 0, ans = 0;

        for (int i = 1; i <= m; i++)

        {

            scanf("%d%d%d", &x, &y, &z);

            addedge(x, y, z), addedge(y, x, z);

            base += z;

        }

        find_cir();

        scanf("%d", &k);

        printf("Case #%d: ", ++t);

        if (block == 0)

        {

            printf("%lld\n", base%MOD); continue;

        }

        for (int i = 1; i <= block; i++)

        {

            sort(cir[i].begin(), cir[i].end(), cmp);

            base -= cir[i][0];

            for (int j = 1; j < cir[i].size(); j++)

                cir[i][j] = cir[i][0] - cir[i][j];

            cir[i][0] = 0;

        }

        int Max = 1;

        for (int i = 1; i <= block && Max < k; i++)

            Max *= cir[i].size();

        if (k > Max)

        {

            k = Max;

            mid = 2e9;

            num = 0;

            dfs(1, 0);

        }

        else

        {

            mid = BinaryFind(1, 2e9);

            mid--;

            num = 0;

            dfs(1, 0);

            for (int i = num+1; i <= k; i++) res[i] = mid+1;

        }

        sort(res+1, res+k+1);

        for (int i = 1; i <= k; i++)

            ans += i * (base+res[i]) % MOD;

        printf("%lld\n", ans% MOD);

    }

}