29405번 - Прыгать! 스페셜 저지다국어

문제

Тигра любит прыгать! К сожалению, прыгать по лесу не очень удобно --- и за кочку можно зацепиться и в дерево врезаться. Умный и добрый Кролик решил помочь Тигре и построить несколько удобных дорог из желтого кирпича (ведь желтый --- любимый цвет Тигры). Для этого он составил полную карту Стоакрового Леса и посчитал какие дороги можно построить, и сколько кирпича на каждую из них потребуется. Оценив запасы кирпича, Кролик понял что возможно вместо некоторых дорог можно построить настоящие лесные автобаны --- широкие дороги, где Тигра сможет разогнаться еще быстрее и получить больше удовольствия от движения. Для постройки автобана вместо обычной дороги потребуется в $c$ раз больше кирпича, независимо от расположения дороги.

Каждая дорога соединяет какие-то два интересных для Тигры места --- домики обитателей Леса, поляны, где он может вдоволь попрыгать и так далее. Кролик пронумеровал интересные места целыми числами от 1ドル$ до $n$ и выписал список возможных дорог. Теперь он хочет построить дорожную сеть таким образом, чтобы было построено как можно больше автобанов, но при этом можно было из каждого интересного места попасть в любое другое. Для реализации этого плана у Кролика в распоряжении есть $k$ кирпичей. Помогите ему спланировать постройку дорог!

입력

Первая строка входного файла содержит четыре целых числа $n,ドル $m,ドル $k$ и $c$ (1ドル \le n, m \le 100000$; 1ドル \le k \le 10^9$; 1ドル \le c \le 1000$) --- количество интересных мест, возможных дорог, общее количество кирпичей и коэффициент, во сколько раз больше кирпичей требуется на постройку автобана, соответственно.

Следующие $m$ строк содержат описания дорог --- три целых числа $a_i,ドル $b_i,ドル $l_i$ (1ドル \le a_i, b_i \le n$; 1ドル \le l_i \le 10^6$) --- номера интересных мест, которые соединяет дорога и количество кирпича, необходимое на постройку этой дороги, соответственно.

Каждая дорога соединяет два различных интересных места. Между двумя интересными местами может быть более одной дороги.

출력

Если невозможно построить такую сеть дорог, то выведите в выходной файл единственное слово <<Impossible>>.

Иначе, в первой строке выходного файла выведите два целых числа $p$ и $q$ --- количество обычных дорог и автобанов в оптимальном плане. Во второй строке выведите $p$ целых чисел --- номера обычных дорог, которые необходимо построить в возрастающем порядке. В третей строке выведите $q$ целых чисел --- номера автобанов, также в возрастающем порядке.

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

제한

힌트