CF362D.Fools and Foolproof Roads

You must have heard all about the Foolland on your Geography lessons. Specifically, you must know that federal structure of this country has been the same for many centuries. The country consists of n cities, some pairs of cities are connected by bidirectional roads, each road is described by its length l__i.

The fools lived in their land joyfully, but a recent revolution changed the king. Now the king is Vasily the Bear. Vasily divided the country cities into regions, so that any two cities of the same region have a path along the roads between them and any two cities of different regions don't have such path. Then Vasily decided to upgrade the road network and construct exactly p new roads in the country. Constructing a road goes like this:

1. We choose a pair of distinct cities u, v that will be connected by a new road (at that, it is possible that there already is a road between these cities).
2. We define the length of the new road: if cities u, v belong to distinct regions, then the length is calculated as min(109, S + 1) (S — the total length of all roads that exist in the linked regions), otherwise we assume that the length equals 1000.
3. We build a road of the specified length between the chosen cities. If the new road connects two distinct regions, after construction of the road these regions are combined into one new region.

Vasily wants the road constructing process to result in the country that consists exactly of q regions. Your task is to come up with such road constructing plan for Vasily that it meets the requirement and minimizes the total length of the built roads.

你一定在地理课上听说过福兰德（Foolland）这个国家。具体来说，你一定知道该国的联邦结构已经延续了数个世纪。该国由 $n$ 座城市组成，其中某些城市对之间由双向道路连接，每条道路具有长度 $l_i$。

愚民们曾在这片土地上幸福地生活着，但一场突如其来的革命改变了国王。如今的国王是瓦西里熊（Vasily the Bear）。瓦西里将全国的城市划分为若干区域，使得：同一区域内的任意两座城市之间都存在一条仅由道路构成的路径；而不同区域的任意两座城市之间则不存在这样的路径。随后，瓦西里决定升级道路网络，在全国恰好新建 $p$ 条道路。新建一条道路的过程如下：

1. 我们选择一对互异的城市 $u$、$v$，将在它们之间新建一条道路（注意：这两座城市之间可能已存在道路）；
2. 我们确定这条新道路的长度：若城市 $u$、$v$ 属于不同的区域，则其长度定义为 $\min(10^9,\, S + 1)$（其中 $S$ 表示这两个被连接区域中所有现有道路的总长度）；否则（即 $u$、$v$ 属于同一区域），其长度定义为 $1000$；
3. 我们在所选城市之间修建一条指定长度的道路。若新建道路连接的是两个不同的区域，则修建完成后，这两个区域将合并为一个新区域。

瓦西里希望道路建设过程最终使全国恰好剩下 $q$ 个区域。你的任务是为瓦西里设计一个满足该要求的道路建设方案，并使得所建道路的总长度最小。

The first line contains four integers n (1 ≤ n ≤ 105), m (0 ≤ m ≤ 105), p (0 ≤ p ≤ 105), q (1 ≤ q ≤ n) — the number of cities in the Foolland, the number of existing roads, the number of roads that are planned to construct and the required number of regions.

Next m lines describe the roads that exist by the moment upgrading of the roads begun. Each of these lines contains three integers x__i, y__i, l__i: x__i, y__i — the numbers of the cities connected by this road (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i), l__i — length of the road (1 ≤ l__i ≤ 109). Note that one pair of cities can be connected with multiple roads.

第一行包含四个整数 $n$（$1 \leq n \leq 10^5$）、$m$（$0 \leq m \leq 10^5$）、$p$（$0 \leq p \leq 10^5$）、$q$（$1 \leq q \leq n$）——分别表示 Foolland 国的城镇数量、当前已存在的道路数量、计划修建的道路数量，以及所要求的区域数量。

接下来的 $m$ 行描述了在道路升级改造开始时已存在的道路。每行包含三个整数 $x_i$、$y_i$、$l_i$：其中 $x_i$、$y_i$ 表示该道路所连接的两个城镇的编号（$1 \leq x_i, y_i \leq n$，且 $x_i \neq y_i$），$l_i$ 表示该道路的长度（$1 \leq l_i \leq 10^9$）。注意：一对城镇之间可能存在多条道路。

If constructing the roads in the required way is impossible, print a single string "NO" (without the quotes). Otherwise, in the first line print word "YES" (without the quotes), and in the next p lines print the road construction plan. Each line of the plan must consist of two distinct integers, giving the numbers of the cities connected by a road. The road must occur in the plan in the order they need to be constructed. If there are multiple optimal solutions, you can print any of them.

如果无法按要求修建道路，则输出一行字符串 "NO"（不带引号）。否则，第一行输出单词 "YES"（不带引号），接下来的 p 行输出道路修建方案。方案中每一行必须包含两个不同的整数，表示由该道路连接的两座城市的编号。道路在方案中出现的顺序即为它们需要被修建的顺序。若存在多个最优解，输出任意一个即可。

Consider the first sample. Before the reform the Foolland consists of four regions. The first region includes cities 1, 2, 3, the second region has cities 4 and 6, the third region has cities 5, 7, 8, the fourth region has city 9. The total length of the roads in these cities is 11, 20, 5 and 0, correspondingly. According to the plan, we first build the road of length 6 between cities 5 and 9, then the road of length 23 between cities 1 and 9. Thus, the total length of the built roads equals 29.

考虑第一个样例。改革前，福兰国由四个区域组成：第一个区域包含城市 1、2、3；第二个区域包含城市 4 和 6；第三个区域包含城市 5、7、8；第四个区域仅包含城市 9。这些区域内道路的总长度分别为 11、20、5 和 0。根据规划，我们首先在城市 5 和 9 之间修建一条长度为 6 的道路，然后在城市 1 和 9 之间修建一条长度为 23 的道路。因此，所修建道路的总长度为 29。