原有翻译过于机翻，有小错误

此处修正

农夫约翰最近一直在在他的农场试种各种类型的草，他发现不同类型的牛，喜欢不同类型的草。然而，他必须注意，在种草时，不同类型的草，要保持足够远的距离，以防止它们混合。他的农场由总共 $N(1\le N\le 2\times 10^5)$ 块田地组成，其中有 $M(1\le M\le 2\times 10^5)$ 对田地中用小路连接。通过这些小路，这些田地**联通**。每条路的长度在 $[1,10^6]$ 范围内。**没有重边**。
对于每个田地，草的品种是 $K$ 种草 $(1\le K\le N)$ 中的一种。然而，随着时间的推移，他可能决定在某些田地将草转变为不同品种，称之为“更新”。他可能会在一段时间内执行多次更新，这些更新都是**累积**的。
在每次更新之后，他想知道具有**不同**草品种的两个田地之间的**最短路径**的长度。也就是说，在具有不同草品种的所有田地中，他想知道哪两个是最接近的。保证农场将**总是具有至少两个**具有不同草品种的田地。



## 输入格式

第一行输入四个整数 $N,M,K,Q$，$Q$ 代表“更新”的次数。

接下来 $M$ 行，输入三个整数 $A,B,L$，代表一条从 $A$ 到 $B$ 的长度为 $L$ 的双向边。

下一行输入 $N$ 个数，每个数代表这块田地一开始种的哪种草（在 $1...K$）范围内。

最后输入 $Q$ 行，每行两个整数 $A,B$ 表示第 $A$ 块田地的草被换成了第 $B$ 品种。



## 输出格式

总共有 $Q$ 行，每行一个整数。

每个更新后，输出不同种类草之间的最短距离。



## 数据范围

$1\le N,M,Q\le 2\times 10^5,1\le K\le N$。

对于所有边，有 $1\le A,B\le N,1\le L\le 10^6$。

对于 30% 的数据，保证每个田地衍生出来的道路条数 $\le 10$。

农夫约翰最近一直在在他的农场试种各种类型的草，他发现不同类型的牛，喜欢不同类型的草。然而，他必须注意，在种草时，不同类型的草，要保持足够远的距离，以防止它们混合。他的农场由总共 $N(1\le N\le 2\times 10^5)$ 块田地组成，其中有 $M(1\le M\le 2\times 10^5)$ 对田地中用小路连接。通过这些小路，这些田地联通。每条路的长度在 $[1,10^6]$ 范围内。没有重边。 对于每个田地，草的品种是 $K$ 种草 $(1\le K\le N)$ 中的一种。然而，随着时间的推移，他可能决定在某些田地将草转变为不同品种，称之为“更新”。他可能会在一段时间内执行多次更新，这些更新都是累积的。 在每次更新之后，他想知道具有不同草品种的两个田地之间的最短路径的长度。也就是说，在具有不同草品种的所有田地中，他想知道哪两个是最接近的。保证农场将总是具有至少两个具有不同草品种的田地。

输入格式

第一行输入四个整数 $N,M,K,Q$，$Q$ 代表“更新”的次数。

接下来 $M$ 行，输入三个整数 $A,B,L$，代表一条从 $A$ 到 $B$ 的长度为 $L$ 的双向边。

下一行输入 $N$ 个数，每个数代表这块田地一开始种的哪种草（在 $1...K$）范围内。

最后输入 $Q$ 行，每行两个整数 $A,B$ 表示第 $A$ 块田地的草被换成了第 $B$ 品种。

输出格式

总共有 $Q$ 行，每行一个整数。

每个更新后，输出不同种类草之间的最短距离。

数据范围

$1\le N,M,Q\le 2\times 10^5,1\le K\le N$。

对于所有边，有 $1\le A,B\le N,1\le L\le 10^6$。

对于 30% 的数据，保证每个田地衍生出来的道路条数 $\le 10$。