Рустэм работает в Лаборатории Суперкомпьютерного Моделирования (ЛСМ) системным администратором локальной сети ВШ ЭКН. Его сеть соединяет множество аудиторий и располагается в нескольких корпусах.
Сеть постоянно расширяется и Рустэму поручено проложить новый участок сети. У него есть схема, на которой указаны все возможные соединения между парами аудиторий и для каждого соединения он знает длину провода, необходимого для его прокладки. Его цель состоит в том, чтобы все аудитории были подключены к сети (возможно через другие аудитории).
С связи с системой госзакупок ЛСМ, в которой работает Рустэм, покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене P5 и P6 рублей за метр. При этом в наличии имеется только Q5 метров кабеля пятой категории и Q6 метров кабеля шестой категории.
Рустэму необходимо составить план постройки сети с наименьшими затратами. План представляет собой список соединений между аудиториями, при этом каждому соединению должно быть приписано, кабель какой категории будет проложен между этими аудиториями (пятой или шестой). Стоимость прокладки этой сети равна сумме стоимости прокладки всех соединений. Общая длина кабеля каждой категории не должна превышать количество кабеля, имеющегося в магазине.
В первой строке входного файла содержится число N — количество аудиторий, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000).
Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.
Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10000).
Если все аудиториии можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N - 1 строк должны содержать описание соединений, представленных двумя числами каждое: Ai и Ci, где Ai — номер соединения в списке возможных соединений (от 1 до M), а Ci задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.
Если все аудитории соединить невозможно выведите слово Impossible.
## Входные Данные
В первой строке входного файла содержится число N — количество аудиторий, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000).Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10000).
## Выходные Данные
Если все аудиториии можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N - 1 строк должны содержать описание соединений, представленных двумя числами каждое: Ai и Ci, где Ai — номер соединения в списке возможных соединений (от 1 до M), а Ci задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.Если все аудитории соединить невозможно выведите слово Impossible.
## Пример
Входные данные6 71 2 72 6 51 4 82 3 53 4 55 6 63 5 32 11 3 100Выходные данные657 52 64 65 61 5
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of auditoriums, $ M \in \mathbb{Z}^+ $ the number of possible connections.
Let $ E = \{ (a_i, b_i, l_i) \mid i \in \{1, \dots, M\} \} $ be the set of possible edges, where $ a_i, b_i \in \{1, \dots, N\} $ are endpoints and $ l_i \in \mathbb{Z}^+ $ is the length of cable required.
Let $ P_5, P_6 \in \mathbb{Z}^+ $ be the cost per meter of Category 5 and 6 cable, respectively.
Let $ Q_5, Q_6 \in \mathbb{Z}^+ $ be the available lengths of Category 5 and 6 cable, respectively.
**Constraints**
1. $ 1 \leq N \leq 1000 $, $ 1 \leq M \leq 10000 $
2. $ 1 \leq l_i \leq 100 $ for all $ i \in \{1, \dots, M\} $
3. $ 1 \leq P_5, P_6, Q_5, Q_6 \leq 10000 $
4. The network must connect all $ N $ nodes (i.e., form a spanning tree).
5. The total length of Category 5 cable used $ \leq Q_5 $.
6. The total length of Category 6 cable used $ \leq Q_6 $.
7. Each edge in the spanning tree is assigned exactly one cable category: 5 or 6.
**Objective**
Find a spanning tree $ T \subseteq E $ with $ N-1 $ edges, and an assignment $ c_i \in \{5,6\} $ for each edge $ i \in T $, minimizing total cost:
$$
\sum_{i \in T} l_i \cdot P_{c_i}
$$
subject to:
$$
\sum_{\substack{i \in T \\ c_i = 5}} l_i \leq Q_5, \quad \sum_{\substack{i \in T \\ c_i = 6}} l_i \leq Q_6
$$
If no such spanning tree exists, output "Impossible".
**Output**
If solution exists:
- First line: total cost
- Next $ N-1 $ lines: $ (i, c_i) $, where $ i $ is the edge index (1-based) and $ c_i \in \{5,6\} $ is the assigned category.
Otherwise: "Impossible".