题目内容

某市交通网络包含 $n$ 个交通枢纽和 $m$ 条双向道路，每条道路通过所需的时间为其权值。为了缓解拥堵，政府计划修建 $k$ 条专用快速通道，每条通道从枢纽 $1$ 直接通往另一个枢纽 $p_i$，通行时间为 $s_i$。

全部原有道路和这 $k$ 条快速通道共同使用时，可以求出从枢纽 $1$ 到其他各个枢纽的最短通行时间。现在需要你对计划进行精简：在保证 $1$ 到其他所有枢纽的最短时间不发生任何改变的前提下，请你计算最多可以取消修建多少条快速通道（即这些通道即使不建，最短时间也不会变化）。

点数 $n$、原有道路数 $m$ 和计划快速通道数 $k$ 均不超过 $10^5$，所有道路及快速通道的通行时间均为正且不超过 $10^9$。

输入描述

第一行包含三个整数 $n, m, k$。 接下来 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示枢纽 $u_i$ 与 $v_i$ 之间有一条通行时间为 $w_i$ 的双向道路。