Jorge is a really friendly person, he is so friendly that he has $$$k$$$ friends! sadly he doesn't know where his friends live. He only knows they are all from a different city. The world of Jorge consist of $$$n$$$ cities enumerated from $$$0$$$ to $$$n-1$$$. Between them there are $$$m$$$ roads, with different lengths, that connect a pair of cities, such that at least one path between every pair of cities exist. Jorge lives in city $$$0$$$, and he wants to know the expected value of the distance to his closest friend (The distance to a friend is the length of the shortest path between city $$$0$$$ and his friend's city).
Given the description of the world, and the number of friends Jorge has, answer the value he wants. Assume all possible arrangements of his $$$k$$$ friends are equiprobable.
The first line of input contains three values separated by a space, $$$N$$$ ($$$1\leq N \leq 10^5$$$), $$$M$$$ ($$$1\leq M\leq min(\frac{n*(n-1)}{2},10^6)$$$), and $$$k$$$ ($$$1\leq k \lt N$$$). Each of the next $$$M$$$ lines contains $$$3$$$ values separated by a space, $$$p_i$$$, $$$q_i$$$, and $$$k_i$$$, ($$$0\leq p_i,q_i\leq N-1, 1\leq k_i\leq 1000$$$) meaning there is a road between city $$$p_i$$$ and $$$q_i$$$ with length $$$k_i$$$.
It can be proven that the answer can be represented as a rational number $$$\frac{p}{q}$$$ with coprime $$$p$$$ and $$$q$$$. You need to output $$$p \cdot q^{-1}$$$ mod $$$10^{9}+7$$$.
2 1 1 0 1 3
3
