描述

随着新一代高速通信网络 Wifeless THU 的诞生,THU 的网速得到了极大的提升。为 了应对来自隔壁的冲击,PKU 决定对现有的校园网 Wireless PKU 进一步升级优化。 现有的 Wireless PKU 通信网络包含 N 个基站和 M 条光缆,每条光缆连接两个基站且长度 已知,这两个基站可以通过这条光缆互相通信。PKU 有两种可以制作光缆的新材料,每种材料有总长度 T 和更换代价 V 两个属性。对一条长度为 L 的现有光缆进行升级优化时,只能选择一种新材料将整段光缆更换,更换所需的代价为 L*V。最终更换成每种新材料的现有光缆的长度之和不能超过这种新材料的总长度 T。 由于资金有限,PKU 只打算对一部分光缆进行升级优化,使得所有基站可以仅通过优化后的光缆通信,并且升级所需的代价尽可能小。请你计算一下这个代价。

输入格式

第一行两个整数 N、M,表示 Wireless PKU 现有的基站数和光缆数。 接下来 M 行每行三个整数 A、B、L,描述一条连接 A、B 两个基站长度为 L 的光缆。 最后一行有四个整数 V1、T1、V2、T2,表示第一种新材料的更换代价和总长度、第二种新材料的更换代价和总长度。

输出格式

一个整数,表示升级所需的最小代价。如果不能满足要求,输出 "Impossible"。

样例输入

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

数据范围与约定

  • 对于 20%的数据,1<=N<=10。
  • 对于 100%的数据,1<=N<=1000,1<=M<=10000,1<=T1,T2,V1,V2<=10000,1<=A,B<=N, 0<=L<=100。