Switch Grass#10530
Farmer John has discovered that different breeds of cows prefer different types of grass. However, the grass must be planted carefully so as not to harm the cows.
John's farm consists of fields, and pairs of fields are connected by bidirectional paths. It is possible to travel from any field to any other field using these paths. Each path has an integer length between and 10^6, inclusive. There is at most one direct path between any pair of fields.
Initially, Farmer John plants one of types of grass in each field. Over time, he may change the type of grass planted in some fields. Such an operation is called an update.
After each update, Farmer John wants to know the length of the shortest path between two fields containing different types of grass. In other words, among all pairs of fields with different grass types, he wants to find the minimum possible distance between them. It is guaranteed that at any moment there is at least one pair of fields with different grass types.
The first line contains four integers: n~(1 \le n \le 2 \cdot 10^5), m~(1 \le m \le 2 \cdot 10^5), k~(1 \le k \le n), and q~(1 \le q \le 2 \cdot 10^5), where is the number of update operations.
The next lines describe the paths. Each line contains three integers , , and , meaning that there is a bidirectional path of length between fields and , where 1 \le a,b \le n.
The next line contains integers describing the initial grass type in each field. Each value is in the range from to .
The following lines each describe one update operation. Each line contains two integers and , meaning that the grass type in field is changed to .
For each update operation, print the length of the shortest path between two fields with different grass types after applying the update.
Example 1