I Curse Myself

Problem Description

There is a connected undirected graph with weights on its edges. It is guaranteed that each edge appears in at most one simple cycle. Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, define $V(k)$ as the weight of the $k$-th smallest weighted spanning tree of this graph, however, $V(k)$ would be defined as zero if there did not exist $k$ different weighted spanning trees. Please calculate $\displaystyle\left(\sum_{k=1}^{K}{k \cdot V(k)}\right) \bmod 2^{32}$.

Input

The input contains multiple test cases. For each test case, the first line contains two positive integers $n, m$ $(2 \leq n \leq 1000, n-1 \leq m \leq 2n-3)$, the number of nodes and the number of edges of this graph. Each of the next $m$ lines contains three positive integers $x, y, z$ $(1 \leq x, y \leq n, 1 \leq z \leq 10^6)$, meaning an edge weighted $z$ between node $x$ and node $y$. There does not exist multi-edge or self-loop in this graph. The last line contains a positive integer $K$ $(1 \leq K \leq 10^5)$.

Output

For each test case, output " Case #$x$: $y$ " in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

Sample Input

4 3

1 2 1

1 3 2

1 4 3

1

3 3

1 2 1

2 3 2

3 1 3

4

6 7

1 2 4

1 3 2

3 5 7

1 5 3

2 4 1

2 6 2

6 4 5

7

Sample Output

Case #1: 6

Case #2: 26

Case #3: 493

Source

2017 Multi-University Training Contest - Team 1