Sum of Exact-Edge Path Lengths in a Weighted Graph

You are given an undirected weighted graph \(G\) with vertices \(1, 2, \ldots, n\) and \(m\) edges. You are also given an integer \(x\). For each integer \(i\) in \(1 \le i \le x\), you need to answer the following query:

What is the minimum total weight of a path that starts at vertex \(1\), ends at vertex \(n\), and uses exactly \(i\) edges?

If such a path does not exist for a given \(i\), its answer is considered to be \(0\). Note that a path is allowed to use an edge multiple times.

Your task is to compute the sum of the answers for all queries \(i = 1, 2, \ldots, x\) modulo \(998244353\).

Note on formulas: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(m\), and \(x\) \((2 \le n \le 100,\; 1 \le m \le 1000,\; 1 \le x \le 1000)\) representing the number of vertices, the number of edges, and the number of queries respectively.

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) \((1 \le u,v \le n,\; 1 \le w \le 10^9)\) indicating that there is an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer: the sum of the answers to the \(x\) queries (i.e. for each \(i=1,2,\ldots,x\)) modulo \(998244353\).

sample

3 3 2
1 2 1
2 3 1
1 3 3

5