問題一覧 > 通常問題

No.1207 グラフX

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 98
作問者 : penguinmanpenguinman / テスター : kaagekaage
13 ProblemId : 4847 / 出題時の順位表
問題文最終更新日: 2020-08-30 13:12:30

問題文

Penguinman は Paken 王国に住んでいます。
Paken 王国は $N$ 個の都市と $M$ 本の道路からなり、各都市には $1$ ~ $N$ までの番号が割り振られています。
$i$ 本目の道路は都市 $x_i$ と都市 $y_i$ を双方向に結び、長さはある $2$ 以上の整数 $X$ を用いて表され、 $X^{z_i}$ です。
それぞれの道路の長さは異なり、具体的には任意の i(1≤i≤N-1) $i(1\leq i\leq M-1)$ (13:12 修正) に対して、$z_i<z_{i+1}$ が成り立ちます。
また、任意の都市から任意の都市まで幾つかの道路を経由して辿り着けることが保証されています。

Paken 王国では交通にかかる時間が問題になっており、政策の一環として全ての $i,j(1≤i<j≤N)$ の選び方における都市 $i,j$ 間の最短距離の長さの総和を求める必要が出てきました。
しかしながらデータの量は膨大で、Paken 王国の人々では求めることができませんでした。
このままだと政策が滞ってしまうので、彼らの代わりに総和を求め、 $10^9+7$ で割った余りを出力してあげてください。

入力

$N\ M\ X$
$x_1\ y_1\ z_1$
:
$x_M\ y_M\ z_M$

・$2≤N≤2×10^5$
・$N-1≤M≤2×10^5$
・$2≤X≤10^9$
・$1≤x_i,y_i≤N$
・$0≤z_i≤10^9$
・$x_i≠y_i$
・$z_i<z_{i+1}$
・任意の都市から任意の都市まで幾つかの道路を使うことで移動できる
・入力は全て整数

出力

答えを1行に出力し、最後に改行してください。

サンプル

サンプル1
入力
3 2 3
1 2 0
2 3 1
出力
8

頂点 $1$ から $2$ までの最短距離は $1$、
頂点 $2$ から $3$ までの最短距離は $3$、
頂点 $1$ から $3$ までの最短距離は $4$
なのでそれらの総和である $8$ を出力します。

サンプル2
入力
5 5 5
1 4 3
2 4 4
3 5 7
2 3 8
2 3 10
出力
2660500

同じ都市対を結ぶ道路が $2$ 本以上ある場合もあります。

サンプル3
入力
6 8 1000000
2 6 10
3 5 11
4 6 23
1 3 26
1 6 30
5 6 48
3 5 88
3 6 100
出力
524978526

$\bmod 10^9+7$で出力することに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。