Problem Background

Ysuperman is preparing a template test for the kids in his kindergarten, and below is a template problem. He hopes you can help him verify the problem.

Problem Description

A new area has built \( n \) cities and plans to construct \( m \) one-way roads. The \( i \)-th road starts at city \( u_i \), ends at city \( v_i \), and has a construction cost of positive integer \( w_i \).

However, an emergency has arisen before the road construction begins. It is necessary to immediately select some of these roads to build so that all city residents can reach at least one of \( k \) designated cities. You want to know the expected minimum construction cost if these \( k \) cities are chosen randomly with equal probability from the \( n \) cities.

To avoid fractional input and output, you only need to output the result modulo \( 998244353 \).

Input Format

The first line contains three non-negative integers \( n \), \( m \), and \( k \), representing the number of cities, the number of planned roads, and the number of designated cities to be chosen, respectively.

The next \( m \) lines each contain three positive integers \( u_i \), \( v_i \), and \( w_i \), describing a planned one-way road.

Output Format

If there exists a way to choose \( k \) cities such that no matter how roads are built, there is always a city that cannot reach any of the \( k \) cities, output -1.

Otherwise, output a single integer representing the result modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

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

Sample Output #1

5

Sample Input #2

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

Sample Output #2

6

Sample Input #3

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

Sample Output #3

160432162

Sample Input #4

4 1 3
2 4 1

Sample Output #4

-1

Notes

Sample 1 Explanation

There are three ways to choose the set of cities:

1. Choose city 1, then build roads \( 2 \to 1 \) and \( 3 \to 1 \) with the minimum cost of \( 2 + 4 = 6 \).
2. Choose city 2, then build roads \( 1 \to 2 \) and \( 3 \to 1 \) with the minimum cost of \( 1 + 4 = 5 \).
3. Choose city 3, then build roads \( 1 \to 2 \) and \( 2 \to 3 \) with the minimum cost of \( 1 + 3 = 4 \).

Thus, the expected minimum cost is \( (6 + 5 + 4) / 3 = 5 \).

Sample 2 Explanation

There are six ways to choose the set of cities:

1. Choose cities 1 and 2, minimum cost is 9.
2. Choose cities 1 and 3, minimum cost is 6.
3. Choose cities 1 and 4, minimum cost is 7.
4. Choose cities 2 and 3, minimum cost is 5.
5. Choose cities 2 and 4, minimum cost is 6.
6. Choose cities 3 and 4, minimum cost is 3.

Thus, the expected minimum cost is \( (9 + 6 + 7 + 5 + 6 + 3) / 6 = 6 \).

Sample 3 Explanation

Due to space constraints, only a diagram is provided:

Sample 4 Explanation

When the set of cities is chosen as 1, 2, and 3, city 4 cannot reach any of 1, 2, or 3, so the answer is -1.

Data Range

For 10% of the data, \( n \leq 15 \), \( m \leq 30 \).

For 30% of the data, \( n \leq 20 \), \( m \leq 50 \).

For another 5% of the data, all \( w_i \) are equal.

For another 5% of the data, \( k = n \).

For another 5% of the data, \( k = n - 1 \).

For another 10% of the data, \( m = n \).

For another 20% of the data, \( k = 1 \).

For 100% of the data, \( 2 \leq n \leq 10^5 \), \( 1 \leq m \leq 2 \times 10^5 \), \( 1 \leq k \leq n \), \( 1 \leq u_i, v_i \leq n \), \( 0 \leq w_i \leq 998244352 \).

见题面 Input 部分

见题面 Output 部分