Farmer John 最近在他的农场尝试种植不同类型的草，发现不同类型的奶牛喜欢不同类型的草。然而，他必须小心确保不同类型的草种植得足够远，以防止它们不可分割地混合在一起。
FJ 的农场由 块田地组成（），其中 对田地通过双向路径连接（）。使用这些路径，可以从任何田地走到任何其他田地。每条路径的长度是一个在 范围内的整数。任何一对田地之间最多只有一条直接路径。
在每块田地中，FJ 最初种植了 种草中的一种（）。然而，随着时间的推移，他可能会决定将某块田地的草更换为另一种类型。他称这种操作为“更新”操作。他可能会在一段时间内执行多次更新，这些更新都是累积性质的。
每次更新后，FJ 想知道种植不同草类型的两块田地之间的最短路径长度。也就是说，在所有种植不同草类型的田地对中，他希望知道哪两块田地最接近。理想情况下，这个数字应该较大，以便他可以防止一种类型的草与另一种类型的草混合。保证农场中始终至少有两块田地种植不同的草类型。
在 30% 的输入案例中，每块田地最多直接连接 10 条路径。
输入的第一行包含四个整数 、、 和 ，其中 是更新的次数（）。
接下来的 行描述路径；每行包含三个整数 、 和 ，表示从田地 到田地 （两者都是 范围内的整数）的长度为 的路径。
接下来的一行表示每块田地最初种植的草类型（ 个 范围内的整数）。
最后，最后的 行每行描述一个更新，由两个整数 和 指定，表示将田地 的草更新为类型 。
对于每次更新，输出更新后种植不同草类型的两块田地之间的最短路径长度。
3 2 3 4 1 2 3 2 3 1 1 1 2 3 3 2 3 1 2 2 2
1 3 3 1