마라톤

$K$명의 KSA 학생들은 벌점 누적에 대한 벌칙으로 마라톤을 하러 왔다. 마라톤 경기장은 $N$개의 체크포인트와 서로 다른 두 체크포인트를 양방향으로 연결하는 $M$개의 길로 이루어져 있다. $i$번 길은 $A_i$번 체크포인트와 $B_i$번 체크포인트를 연결하고, 이 길을 지나는 데 $C_i$의 시간이 걸린다. 임의의 체크포인트에서 다른 체크포인트로 가는 경로는 항상 존재한다.

학생들은 $1$번 체크포인트를 출발해서 $N$번 체크포인트에서 마라톤을 끝내야 한다. $j$번 학생은 초기에 벌점이 $j$점이고 체크포인트를 한 번 지날 때마다 벌점을 $1$점 감점받는다. 이때, 처음 출발하는 $1$번 체크포인트와 $N$번 체크포인트에서도 벌점이 감점되며, 같은 체크포인트를 여러 번 지나도 된다. 단, 길 중간에서 되돌아올 수는 없다.

학생들은 벌점이 $0$점이 된 이후에 체크포인트를 지나서는 안 되며, 마라톤이 끝났을 때 벌점이 정확히 $0$점이어야 한다. 빨리 쉬고 싶은 학생들을 위해 각 학생이 마라톤을 끝내기 위한 최소 시간을 구해보자.

첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다.

$i+1$번째 줄에 세 정수 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다. $(1 \leq i \leq M)$

$i$번 학생이 마라톤을 끝내기 위한 최소 시간을 $D_i$라고 할 때, $D_1 + D_2 + \cdots + D_K$를 $998244353$으로 나눈 나머지를 출력한다.

단, $i$번 학생이 마라톤을 끝낼 방법이 없는 경우에는 $D_i=0$이다.

• $2 \leq N \leq 1500$
• $N-1 \leq M \leq 3000$
• $1 \leq K \leq 10^9$
• $1 \leq A_i < B_i \leq N$ ($1 \leq i \leq M$)
• $1 \leq C_i \leq 10^9$ ($1 \leq i \leq M$)
• $(A_i, B_i) \neq (A_j, B_j)$ $(1 \leq i < j \leq M)$
• $1 \leq i < j \leq N$인 모든 $i$, $j$에 대해서 $i$번 체크포인트와 $j$번 체크포인트를 연결하는 경로가 존재