CF1366F.Jog Around The Graph

You are given a simple weighted connected undirected graph, consisting of $n$ vertices and $m$ edges.

A path in the graph of length $k$ is a sequence of $k+1$ vertices $v_1, v_2, \dots, v_{k+1}$ such that for each $i$ $(1 \le i \le k)$ the edge $(v_i, v_{i+1})$ is present in the graph. A path from some vertex $v$ also has vertex $v_1=v$. Note that edges and vertices are allowed to be included in the path multiple times.

The weight of the path is the total weight of edges in it.

For each $i$ from $1$ to $q$ consider a path from vertex $1$ of length $i$ of the maximum weight. What is the sum of weights of these $q$ paths?

Answer can be quite large, so print it modulo $10^9+7$.

给你一个简单带权连通无向图，包含 $n$ 个顶点和 $m$ 条边。

图中一条长度为 $k$ 的路径是指一个由 $k+1$ 个顶点组成的序列 $v_1, v_2, \dots, v_{k+1}$，使得对每个 $i$（$1 \le i \le k$），边 $(v_i, v_{i+1})$ 均存在于图中。从某个顶点 $v$ 出发的路径满足 $v_1 = v$。注意：路径中允许重复经过同一条边或同一个顶点。

路径的权重定义为该路径中所有边的权重之和。

对每个 $i$（从 $1$ 到 $q$），考虑从顶点 $1$ 出发、长度为 $i$ 的最大权重路径。求这 $q$ 条路径的权重之和。

答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

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.

第一行包含三个整数 $n$、$m$、$q$（$2 \le n \le 2000$；$n - 1 \le m \le 2000$；$m \le q \le 10^9$）——分别表示图中顶点的数量、边的数量，以及答案中应包含的长度个数。

接下来的 $m$ 行每行描述一条边：三个整数 $v$、$u$、$w$（$1 \le v, u \le n$；$1 \le w \le 10^6$）——顶点 $v$ 与 $u$ 之间由一条权重为 $w$ 的无向边相连。图中不含自环和重边。保证所给边构成一个连通图。

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$.

输出一个整数——从顶点 $1$ 出发的长度分别为 $1, 2, \dots, q$ 的最大权路径的权重之和，对 $10^9+7$ 取模。

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$.

第一个示例的图如下所示：

若干条最大权路径为：

• 长度 $1$：边 $(1, 7)$ — 权重 $3$；
• 长度 $2$：边 $(1, 2), (2, 3)$ — 权重 $1+10=11$；
• 长度 $3$：边 $(1, 5), (5, 6), (6, 4)$ — 权重 $2+7+15=24$；
• 长度 $4$：边 $(1, 5), (5, 6), (6, 4), (6, 4)$ — 权重 $2+7+15+15=39$；
• $\dots$

因此答案为 $25$ 项之和：$3+11+24+39+\dots$

在第二个示例中，最大权路径的权重分别为 $4$、$8$、$12$、$16$ 和 $20$。