I Curse Myself

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码