P8950 [YsOI2022] Road Construction

Ysuperman is preparing a template test for the children in his kindergarten. Below is a template problem, and he hopes you can help him verify it.

A place has newly built $n$ cities, and it is planned to build $m$ **directed** roads. For the $i$-th road, the start is $u_i$, the end is $v_i$, and the construction cost is a positive integer $w_i$. However, before construction starts, an emergency happens. You must immediately choose some of these roads to build so that people in every city can reach some set of $k$ cities (that is, people in every city can reach **at least one** of these $k$ cities). You want to know: if these $k$ cities are chosen uniformly at random among the $n$ cities, what is the expected minimum construction cost. To avoid fraction input/output, you only need to output the result modulo $998244353$.

The first line contains three non-negative integers $n,m,k$, representing the number of cities, the number of planned roads, and the number of cities to be chosen. The next $m$ lines each contain three positive integers $u_i,v_i,w_i$, describing a planned directed road.

In particular, if there exists a way to choose $k$ cities such that no matter how you build roads, there will always be some city that cannot reach any of these $k$ cities, output `-1`. Otherwise, output one integer in a single line, representing the answer modulo $998244353$.

#### Sample 1 Explanation There are three ways to choose the set of cities: 1. Choose city $1$. Then building roads $2\to 1,3\to 1$ has the minimum cost, which is $2+4=6$. 2. Choose city $2$. Then building roads $1\to 2,3\to 1$ has the minimum cost, which is $1+4=5$. 3. Choose city $3$. Then building roads $1\to 2,2\to 3$ has the minimum cost, which is $1+3=4$. So the expected minimum cost is $(6+5+4)/3=5$. #### Sample 2 Explanation There are $6$ ways to choose the set of cities: 1. Choose cities $1,2$, minimum cost $9$. 2. Choose cities $1,3$, minimum cost $6$. 3. Choose cities $1,4$, minimum cost $7$. 4. Choose cities $2,3$, minimum cost $5$. 5. Choose cities $2,4$, minimum cost $6$. 6. Choose cities $3,4$, minimum cost $3$. So the expected minimum cost is $(9+6+7+5+6+3)\div 6=6$. #### Sample 3 Explanation It is too small to write here, so here is a diagram:  #### Sample 4 Explanation When the set of cities is chosen as $1,2,3$, city $4$ cannot reach any of $1,2,3$ no matter what, so the answer is $-1$. #### Constraints For $10\%$ of the testdata, $n\le 15$, $m\le 30$. For $30\%$ of the testdata, $n\le 20$, $m\le 50$. For another $5\%$ of the testdata, all $w_i$ are equal. For another $5\%$ of the testdata, $k=n$. For another $5\%$ of the testdata, $k=n-1$. For another $10\%$ of the testdata, $m=n$. For another $20\%$ of the testdata, $k=1$. For $100\%$ of the testdata, $2\le n\le 10^5$, $1\le m\le 2\times 10^5$, $1\le k\le n$, $1\le u_i,v_i\le n$, $0\le w_i\le 998244352$. # Input Format # Output Format # Hint Translated by ChatGPT 5