小红有一张包含 个顶点、 条无向加权边的连通图，第 条边的权值为 。她计划额外修建 条从 号点出发、终点为某些顶点的 双向道路，其中第 条计划道路连接 ，长度为 。 假设修完全部 条道路后，从 号点到其余各点的最短距离依次为 。现在小红想删除尽可能多的计划道路，但要求删除后图中从 号点到每个顶点的最短距离仍然保持为 。请计算最多可以删去的道路数量。

输入描述:

第一行输入三个整数 —— 图的顶点数、边数以及计划道路数。 接下来 行，第 行输入三个整数 ，表示一条连接 与 的无向边，其权值为 。 随后 行，第 行输入两个整数 ，表示一条计划修建的道路 ，长度为 。

输出描述:

输出一个整数，代表最多可以不修建的道路数量。