U401575 test4

有 $n$ 个点，$m$ 条无向边，在求最短路的途中，你可以使用 $k$ 次作弊，使得该路径上的权值除以 $2$ 向下取整，但不得在同一路径上多次使用。

输入 $3$ 个整数 $n,m,k$。 输入 $m$ 行，每行 $3$ 个整数 $u,v,w$，表示连接 $u,v$ 之间的路径权值为 $w$。

输出从 $1$ 到 $n$ 最短路权值之和。因为数据过大，希望你对答案取模 $1145141$。

对于 $100\%$ 的数据，保证 $1\le n,k,m\le10^{3},1\le u_i,v_i\le n,1\le w\le 10^{5}$