마라톤

$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$번 체크포인트를 잇는 경로가 존재한다.