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 $(\\sum_{k = 1}^{K} k dot.op V (k)) bmod 2^(32)$.
The input contains multiple test cases.
For each test case, the first line contains two integers $n$, $m$ ($2 <= n <= 1000$, $n -1 <= m <= 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 <= x, y <= n$, $1 <= z <= 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 <= K <= 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.
## Input
The input contains multiple test cases.For each test case, the first line contains two integers $n$, $m$ ($2 <= n <= 1000$, $n -1 <= m <= 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 <= x, y <= n$, $1 <= z <= 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 <= K <= 10^5$).It is guaranteed that the sum of $K$ in all test cases is no more than $10^6$.
## 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 to the corresponding case.
[samples]
**Definitions**
Let $ G = (V, E) $ be a connected undirected graph with $ |V| = n $, $ |E| = m $, and edge weights $ w: E \to \mathbb{Z}^+ $.
Assume $ G $ is a cactus graph (each edge belongs to at most one simple cycle).
Let $ \mathcal{T} $ be the set of all spanning trees of $ G $, and let $ W(T) = \sum_{e \in T} w(e) $ denote the weight of spanning tree $ T \in \mathcal{T} $.
Let $ V(k) $ be the weight of the $ k $-th smallest spanning tree by weight (i.e., the $ k $-th smallest value in the multiset $ \{ W(T) \mid T \in \mathcal{T} \} $), and $ V(k) = 0 $ if $ |\mathcal{T}| < k $.
**Constraints**
1. $ 2 \le n \le 1000 $, $ n-1 \le m \le 2n-3 $
2. Edge weights satisfy $ 1 \le w(e) \le 10^6 $
3. $ 1 \le K \le 10^5 $, and the sum of $ K $ across test cases $ \le 10^6 $
**Objective**
For each test case, compute:
$$
\left( \sum_{k=1}^{K} k \cdot V(k) \right) \bmod 2^{32}
$$