{"raw_statement":[{"iden":"statement","content":"You are given a connected undirected graph having weighted edges, where it is guaranteed that each edge belongs to at most one simple cycle.\n\nAssuming 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.\n\nPlease calculate $(\\\\sum_{k = 1}^{K} k dot.op V (k)) bmod 2^(32)$.\n\nThe input contains multiple test cases.\n\nFor 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.\n\nEach 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.\n\nThe last line contains an integer $K$ ($1 <= K <= 10^5$).\n\nIt is guaranteed that the sum of $K$ in all test cases is no more than $10^6$.\n\nFor 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.\n\n"},{"iden":"input","content":"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$."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ |V| = n $, $ |E| = m $, and edge weights $ w: E \\to \\mathbb{Z}^+ $.  \nAssume $ G $ is a cactus graph (each edge belongs to at most one simple cycle).  \n\nLet $ \\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} $.  \nLet $ 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 $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 1000 $, $ n-1 \\le m \\le 2n-3 $  \n2. Edge weights satisfy $ 1 \\le w(e) \\le 10^6 $  \n3. $ 1 \\le K \\le 10^5 $, and the sum of $ K $ across test cases $ \\le 10^6 $  \n\n**Objective**  \nFor each test case, compute:  \n$$\n\\left( \\sum_{k=1}^{K} k \\cdot V(k) \\right) \\bmod 2^{32}\n$$","simple_statement":"You are given a connected undirected graph with weighted edges, where each edge is in at most one cycle. Find the sum of k * V(k) for k from 1 to K, modulo 2^32, where V(k) is the weight of the k-th smallest spanning tree (or 0 if there are fewer than k spanning trees).","has_page_source":false}