406064: GYM102253 I I Curse Myself

You are given a connected undirected graph having weighted edges, where it is guaranteed that each edge belongs to at most one simple cycle.

Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, we define $$$V(k)$$$ as the weight of the $$$k$$$-th smallest weighted spanning tree obtained from this graph, or in case that there are only less than $$$k$$$ different weighted spanning trees, we define $$$V(k)$$$ as zero.

Please calculate $$$\left(\sum\limits_{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 integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 1000$$$, $$$n - 1 \leq m \leq 2 n - 3$$$), indicating the number of nodes and the number of edges in this graph respectively.

Each of the next $$$m$$$ lines contains three integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$1 \leq x, y \leq n$$$, $$$1 \leq z \leq 10^6$$$), representing an edge of weight $$$z$$$ between the $$$x$$$-th node and the $$$y$$$-th one. It is guaranteed that no multi-edges or self-loops are permitted in this graph.

The last line contains an integer $$$K$$$ ($$$1 \leq K \leq 10^5$$$).

It is guaranteed that the sum of $$$K$$$ in all test cases is no more than $$$10^6$$$.

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 to the corresponding case.

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

Case #1: 6
Case #2: 26
Case #3: 493