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}$.

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)$.

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.