题目背景

Alex 是 Domestic Networks Inc. 的系统管理员。公司的网络连接着许多公寓，并横跨多栋建筑。随着网络不断扩张，他需要为一片新的区域设计网络连接方案。

题目描述

地图上有 $n$ 个需要接入网络的公寓，以及 $m$ 条可以建设的连接。第 $i$ 条连接连接公寓 $a_i$ 与 $b_i$，长度为 $l_i$ 米。

Alex 需要选择若干条连接，使所有公寓彼此连通（可以经过其他公寓间接连通）。

商店只出售两种网线：

• 五类线：每米价格为 $p_5$，库存为 $q_5$ 米；
• 六类线：每米价格为 $p_6$，库存为 $q_6$ 米。

每条被建设的连接必须完整地使用同一种类别的网线，不能将一条连接拆成多段并混用不同类别。方案中使用的每类网线总长度不能超过相应库存。

请构造一个总费用最小的可行网络建设方案。

输入格式

第一行包含两个整数 $n,m$，分别表示公寓数量和可选连接数量。

接下来 $m$ 行，每行包含三个整数 $a_i,b_i,l_i$，表示第 $i$ 条连接的两个端点以及长度。连接按照输入顺序编号为 $1\sim m$。

最后一行包含四个整数 $p_5,q_5,p_6,q_6$，分别表示五类线的每米价格、库存，以及六类线的每米价格、库存。

输出格式

若不存在满足条件的方案，输出：

Impossible

否则输出共 $n$ 行：

• 第一行输出最小总费用；
• 接下来 $n-1$ 行，每行输出两个整数 $a_i,c_i$，表示选择编号为 $a_i$ 的连接，并使用类别 $c_i\in\{5,6\}$ 的网线。

若存在多个最优方案，输出任意一个。

样例

输入

6 7
1 2 7
2 6 5
1 4 8
2 3 5
3 4 5
5 6 6
3 5 3
2 11 3 100

输出

65
1 5
2 6
4 6
5 6
7 5

数据范围

• $1\le n\le 1000$；
• $1\le m\le 10000$；
• $0\le l_i\le 100$；
• $1\le p_5,q_5,p_6,q_6\le 10000$。