29254번 - История 스페셜 저지다국어

Будучи мастером перевоплощений, Один часто является людям в различных образах. Чаще всего --- в образе старца в синем плаще и войлочной шапке, в сопровождении двух воронов или двух волков, вооружённый копьём. Считалось, что под видом бедного странника или уродливого карлика он бродит по свету, и плохо будет тому, кто, забыв законы гостеприимства, оттолкнёт его от своего порога. Жители Скандинавии верили, что он часто объезжает на своём коне землю или, невидимый для людей, принимает участие в их сражениях, помогая достойнейшим одержать победу.

Когда Один приходит к кому-то в гости, то, конечно же, рассказывает различные истории. Ни для кого не секрет, что его любимая история --- это история про то, как он участвовал в соревнованиях по программированию. Его любимая задача была такая: дан связный, неориентированный, взвешенный граф без кратных ребер и петель, в котором нужно выбрать $N-1$ ребро чтобы используя эти ребра можно было добраться из любой врешины в любую другую, при этом суммарный вес выбраных ребер должен быть минимален. Собственно, этот суммарный вес ему и нужно было предоставить жюри, как ответ.

Один хорошо помнит, что на тест жюри его программа выводила число $S$, но вот сам тест никак не может вспомнить, кроме того, что в графе было $N$ вершин, $M$ ребер и что веса ребер были натуральными числами не больше $R$. Помогите Одину: постройте граф, удовлетворяющий всем этим критериям, или установите, что Один дал противоречивые данные.

Первая строка входного файла содержит четыре целых числа $N$, $M$, $S$ и $R$ ($1\le N\le 10^5$,$1\le M\le 10^5$,$1\le R\le 10^4$,$|S|\le 10^9$), разделенные пробелами.

Если Один дал вам противоречивые данные, то выведите $-1$, иначе выведите $M$ строк с описанием ребер искомого графа. Каждое ребро задается тройкой целых чисел $U$, $V$ и $W$, которые означают, что вершины $U$ и $V$ соединены ребром весом $W$.