#include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int N=1e4+;

 const int M=2e3+;

 const ll mod=(ll)pow(,);

 struct node{

     int u,v,d;

     int next;

 }edge[*N];

 struct NODE

 {

     int v,now;    //value is (v), now add with (now)

     friend bool operator<(NODE x,NODE y)

     {

         return x.v < y.v;

     }

 };//small to big

 priority_queue<NODE> Q;

 int num;

 int head[N];

 int n,m,k;

 ll ans;

 int snum;

 int stk[N],lstk;

 bool instk[M];

 vector<int> s[N];

 int val[M][M];

 vector<int> f,tmpf;

 ll sum_of_edge;

 ll du[M];

 bool cmp(int a,int b)

 {

     return a>b;

 }

 void addedge(int u,int v,int d)

 {

     edge[num].u=u;

     edge[num].v=v;

     edge[num].d=d;

     edge[num].next=head[u];

     head[u]=num++;

 }

 void init()

 {

     num=;                  //记得初始化

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

        memset(du,,sizeof(du));

        snum=;

     lstk=;

     memset(instk,,(n+)*sizeof(bool));

     for(int i=;i<=n;i++)

         s[i].clear();

     ans=;

     sum_of_edge=;

 }

 void dfs(int rt,int fa)

 {

     int v;

     if(instk[rt])

     {

         snum++;

         int sav=rt;

         int sav_lstk=lstk;

         while(stk[lstk]!=rt)

         {

             s[snum].push_back(val[sav][stk[lstk]]);

             sav=stk[lstk--];

         }

         s[snum].push_back(val[sav][stk[lstk]]);

         lstk=sav_lstk;

         return ;

     }

     instk[rt]=;

     stk[++lstk]=rt;

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

     {

         v=edge[i].v;

         if(v==fa || du[v]==) continue;

         du[rt]--; du[v]--;

         dfs(v,rt);

     }

     instk[rt]=;

     lstk--;

 }

 void merge()

 {

     NODE q;

     int i,j,cnt;

     f.clear();

     if(snum==)

     {

         f.push_back();

         return  ;

     }

     for(int i=;i<s[].size();i++)

         f.push_back(s[][i]);

     for(int i=;i<=snum;i++)

     {

         cnt=f.size()*s[i].size();

         if(cnt>k) cnt=k;

         while(!Q.empty())

             Q.pop();

         for(j=;j<s[i].size();j++)

         {

             q.v=s[i][j]+f[];

             q.now=;

             Q.push(q);

         }

         tmpf.clear();

         while(cnt--)

         {

             q=Q.top();

             Q.pop();

             tmpf.push_back(q.v);

             if(q.now!=f.size()-)

             {

                 q.v-=f[q.now];

                 q.now++;

                 q.v+=f[q.now];

                 Q.push(q);

             }

         }

         swap(f,tmpf);

     }

 //    cout<<"check merge\n";

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

 //        printf("%d ",f[i]);

 //    printf("\n");

 //    printf("end of check of merge\n");

 }

 void solve()

 {

     dfs(,-);

     for(int i=;i<=snum;i++)

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

 //    printf("check s\n");

 //    for(int i=1;i<=snum;i++)

 //    {

 //        for(int j=0;j<s[i].size();j++)

 //            printf("%d",s[i][j]);

 //        printf("\n");

 //    }

 //    printf("end of check of s\n");

     merge();

 }          

 int main()

 {

     int cas=,a,b,c;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         init();

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

         {

             scanf("%d%d%d",&a,&b,&c);

             addedge(a,b,c);

             addedge(b,a,c);

             du[a]++; du[b]++;

             val[a][b]=val[b][a]=c;

             sum_of_edge+=c;

         }

         scanf("%d",&k);

         solve();

         for(int i=;i<f.size();i++)

             ans=(ans+1ll*(i+)*(sum_of_edge-f[i])%mod)%mod;

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

     }

     return ;

 }