小红有一个 个点 条边的无向图，每条边有一个权值 。小红现在计划修 条双向道路，起点是 1 号点，终点是其他顶点。假设修了这 条路后，从 1 号点到其他点的距离为 ，小红想知道，可以少修多少条路，使得从 1 号点到其他点的距离仍然为 。

输入描述:

第一行三个整数 ，表示点数，边数，以及小红计划修的路数。接下来 行，每行三个整数 ，表示一条边的两个端点以及权值。接下来 行，每行两个整数 ，表示计划修从 1 号点到 号点的一条路，长度为 。

输出描述:

输出一个整数，表示可以少修的路数。