每天，FJ 需要经过一些道路去检查牛棚 里面的牛。农场上有 条双向泥土道路，编号为 。道路 连接牛棚 和 。FJ 需要 时间单位用道路 从 走到 或者从 走到 。
他想更新一些路经来减少每天花在路上的时间。具体地说，他想更新 条路经，将它们所须时间减为 。帮助 FJ 选择哪些路经需要更新使得从 到 的时间尽量少。
第一行：三个空格分开的数：。 第 行：第 行有三个空格分开的数：。
4 4 1 1 2 10 2 4 10 1 3 1 3 4 100
1
对于 的数据，，，，，。
样例中 是 ，更新道路 使得从 到 的时间由 减少到 。 最新最短路经是 ，总用时为 单位。
Usaco2009 Feb Gold
