Jog Around The Graph

Description:

Input:

The first line contains a three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 2000$$$; $$$n - 1 \le m \le 2000$$$; $$$m \le q \le 10^9$$$) — the number of vertices in the graph, the number of edges in the graph and the number of lengths that should be included in the answer.

Each of the next $$$m$$$ lines contains a description of an edge: three integers $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \le v, u \le n$$$; $$$1 \le w \le 10^6$$$) — two vertices $$$v$$$ and $$$u$$$ are connected by an undirected edge with weight $$$w$$$. The graph contains no loops and no multiple edges. It is guaranteed that the given edges form a connected graph.

Output:

Print a single integer — the sum of the weights of the paths from vertex $$$1$$$ of maximum weights of lengths $$$1, 2, \dots, q$$$ modulo $$$10^9+7$$$.

Sample Input:

7 8 25
1 2 1
2 3 10
3 4 2
1 5 2
5 6 7
6 4 15
5 3 1
1 7 3

Sample Output:

4361

Sample Input:

2 1 5
1 2 4

Sample Output:

60

Sample Input:

15 15 23
13 10 12
11 14 12
2 15 5
4 10 8
10 2 4
10 7 5
3 10 1
5 6 11
1 13 8
9 15 4
4 2 9
11 15 1
11 12 14
10 8 12
3 6 11

Sample Output:

3250

Sample Input:

5 10 10000000
2 4 798
1 5 824
5 2 558
4 1 288
3 4 1890
3 1 134
2 3 1485
4 5 284
3 5 1025
1 2 649

Sample Output:

768500592

Note:

Here is the graph for the first example:

Some maximum weight paths are:

• length $$$1$$$: edges $$$(1, 7)$$$ — weight $$$3$$$;
• length $$$2$$$: edges $$$(1, 2), (2, 3)$$$ — weight $$$1+10=11$$$;
• length $$$3$$$: edges $$$(1, 5), (5, 6), (6, 4)$$$ — weight $$$2+7+15=24$$$;
• length $$$4$$$: edges $$$(1, 5), (5, 6), (6, 4), (6, 4)$$$ — weight $$$2+7+15+15=39$$$;
• $$$\dots$$$

So the answer is the sum of $$$25$$$ terms: $$$3+11+24+39+\dots$$$

In the second example the maximum weight paths have weights $$$4$$$, $$$8$$$, $$$12$$$, $$$16$$$ and $$$20$$$.