#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
#define PI acosI(-1.0)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e3+100,maxm=1e5+100,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=1e13+7;


struct is
{
    int x,r;
    bool operator <(const is &c)const
    {
        return x<c.x;
    }
};
int d[maxn],n,m,k;
inline void update(vector<int>&a,vector<int>&b)
{
    priority_queue<is>q;
    for(int i=0;i<b.size();i++)
        d[i] = 0,q.push((is){a[0]+b[i],i});
    vector<int>ans;
    for(int i=1;i<=k;i++)
    {
        if(q.empty())break;
        is x=q.top();
        q.pop();
        ans.push_back(x.x);
        if(d[x.r]+1<a.size())
            q.push((is){a[++d[x.r]]+b[x.r],x.r});
    }
    a=ans;
}
int cmp(int x,int y)
{
    return x>y;
}
struct edge
{
    int from,to,d,nex;
}G[maxn<<2];
int head[maxn],edg;
inline void addedge(int u,int v,int d)
{
    G[++edg]=(edge){u,v,d,head[u]},head[u]=edg;
    G[++edg]=(edge){v,u,d,head[v]},head[v]=edg;
}
int pre[maxn],bccno[maxn];
int dfs_clock,bcc_cnt;
stack<int>s;
vector<int>ans,fuck;
inline int dfs(int u,int fa)
{
    int lowu=++dfs_clock;
    pre[u]=dfs_clock;
    int child=0;
    for(int i=head[u]; i!=-1; i=G[i].nex)
    {
        int v=G[i].to;
        edge e=G[i];
        if(!pre[v])
        {
            s.push(i);
            child++;
            int lowv=dfs(v,u);
            lowu=min(lowu,lowv);
            if(lowv>=pre[u])
            {
                bcc_cnt++;
                fuck.clear();
                while(true)
                {
                    int e=s.top();
                    s.pop();
                    fuck.push_back(G[e].d);
                    if(bccno[G[e].from]!=bcc_cnt)
                        bccno[G[e].from]=bcc_cnt;
                    if(bccno[G[e].to]!=bcc_cnt)
                        bccno[G[e].to]=bcc_cnt;
                    if(G[e].from==u&&G[e].to==v) break;
                }
                if(fuck.size()>1)update(ans,fuck);
            }
        }
        else if(pre[v]<pre[u]&&v!=fa)
        {
            s.push(i);
            lowu=min(lowu,pre[v]);
        }
    }
    return lowu;
}
void init()
{
    dfs_clock=bcc_cnt=edg=0;
    for(int i=0;i<=n;i++)
        head[i]=-1,bccno[i]=0,pre[i]=0;
    ans.clear();
    ans.push_back(0);
}


int main()
{
    int cas=1;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        ll sumsum=0;
        for(int i=1; i<=m; i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            sumsum+=z;
            addedge(x,y,z);
        }
        scanf("%d",&k);
        dfs(1,-1);
        ll out=0,MOD=(1LL<<32);
        printf("Case #%d: ",cas++);

        for(int i=1;i<=k;i++)
        {
            if(i-1>=ans.size())break;
            out+=1LL*(sumsum-ans[i-1])*i;
            out%=MOD;
        }
        printf("%lld\n",out);
    }
    return 0;
}