D. Дураки и дороги
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На уроках географии в школе Вам наверняка рассказывали о Стране Дураков. В частности, Вы должны знать, что внутреннее устройство Страны Дураков не менялось на протяжении многих столетий. Страна состоит из n городов, некоторые пары которых соединены двусторонними дорогами, причем каждая из дорог характеризуется величиной li — своей длиной.

Так и жили бы дураки, но недавно в результате государственного переворота в стране поменялся король — им стал медведь Василий. Василий разделил города страны на области таким образом, что между любыми двумя городами из одной области существует путь по дорогам страны, а между двумя городами из разных областей такого пути нет. После этого Василий решил провести дорожную реформу: построить в стране ровно p новых дорог. Строительство одной дороги происходит следующим образом:

  1. Выбирается пара различных городов u, v, которые будет соединять новая дорога (при этом возможно, что между этими городами уже существует дорога).
  2. Определяется длина новой дороги: если города u, v относятся к различным областям, то длина вычисляется как min(109, S + 1) (S — суммарная длина всех дорог, существующих в соединяемых областях), иначе длина полагается равной 1000.
  3. Между выбранными городами строится дорога указанной длины. Если новая дорога соединяла различные области, то после ее строительства эти две области будут объединены в одну.

Василий хочет, чтобы после проведения дорожной реформы страна состояла ровно из q областей. Ваша задача — разработать для медведя Василия такой план строительства дорог, удовлетворяющий этому требованию, чтобы суммарная длина построенных дорог была минимально возможной.

Входные данные

В первой строке записано четыре целых числа n (1 ≤ n ≤ 105), m (0 ≤ m ≤ 105), p (0 ≤ p ≤ 105), q (1 ≤ q ≤ n) — количество городов в Стране Дураков, количество существующих дорог, количество дорог, которые планируется построить, и требуемое количество областей.

В следующих m строках описываются дороги, существующие на момент начала реформы. Каждая из этих строк содержит три целых числа xi, yi, li: xi, yi — номера городов, которые соединяет дорога (1 ≤ xi, yi ≤ n, xi ≠ yi), li — ее длина (1 ≤ li ≤ 109). Обратите внимание, что одна и та же пара городов может быть соединена несколькими дорогами.

Выходные данные

Если невозможно требуемым образом построить дороги, выведите единственную строку «NO» (без кавычек). В противном случае выведите в первую строку слово «YES» (без кавычек), а в следующих p строках приведите план строительства дорог. Каждая строка плана должна состоять из двух различных целых чисел, задающих номера городов, которые соединяет очередная дорога. Дороги в плане должны следовать в том порядке, в котором их нужно строить. Если существует несколько оптимальных решений, можно вывести любое.

Примеры
Входные данные
9 6 2 2
1 2 2
3 2 1
4 6 20
1 3 8
7 8 3
5 7 2
Выходные данные
YES
9 5
1 9
Входные данные
2 0 1 2
Выходные данные
NO
Входные данные
2 0 0 2
Выходные данные
YES
Примечание

Рассмотрим первый пример. До начала реформы Страна Дураков состоит из четырех областей. Первая область включает в себя города 1, 2, 3, вторая — города 4 и 6, третья — города 5, 7, 8, четвертая — город 9. Суммарная длина дорог, существующих в этих областях, составляет 11, 20, 5 и 0 соответственно. Согласно плану, первой строится дорога длины 6 между городами 5 и 9, а второй — дорога длины 23 между городами 1 и 9. Таким образом, суммарная длина построенных дорог составляет 29.