You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Statement

有 $n$ 位裁判和 $m$ 场比赛。每场比赛由两位不同的裁判监督（可能存在裁判不监督比赛），若某场比赛的两位裁判均被同一家公司买通，该公司将获得对应比赛的收益。A 和 B 两家公司轮流行动（A 先手），每轮行动可以执行以下操作之一：

1. 买通未被买通的裁判：无需代价，该裁判归属当前公司。
2. 买通对方已买通的裁判：假设对方上次买通该裁判的代价为 $c$，当前公司需支付 $c + k$ 的代价。支付后，该裁判归属当前公司，且 $c + k$ 将作为下次买通的基准代价。
3. 跳过行动：公司可以跳过自己的回合。

每家公司的总收益为获得的比赛收益总和 减去 买通裁判支付的所有代价。求在双方均采取最优策略最大化自己与对方的总收益的差值时，A的收益减去B的收益的值。

输入格式

第一行输入三个整数 $n, m, k$（$1 \leq n, m \leq 10^6$，$1 \leq k \leq 10^9$）。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$，$1 \leq w_i \leq 10^9$），表示第 $i$ 场比赛的两位裁判及收益。

输出格式

输出一个整数，表示 A 的收益减去 B 的收益的最终差值。

样例

Sample 1

Input

3 2 3
1 2 4
2 3 2

Output

1

子任务

对于所有子任务，未指明的，以输入格式中说明的为准。

对于子任务之间，不存在依赖

子任务1 (15 pts)

子任务2 (20 pts)

子任务3 (5 pts)

子任务4 (20 pts)

子任务5 (40 pts)

无额外限制