Background

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.

Problem Description

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$.

Input Format

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.

Output Format

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$.

3 4 1
1 2 1
2 1 2
2 3 3
3 1 4

5

4 6 2
1 2 1
1 3 3
2 3 2
3 4 5
4 1 4
4 2 6

6

8 16 3
5 6 7
7 2 10
4 6 4
5 7 5
8 4 12
1 3 8
2 3 6
4 1 8
1 7 2
8 3 1
2 5 3
6 4 11
7 3 14
3 8 9
8 1 13
6 7 16

160432162

4 1 3
2 4 1

-1

Hint

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