국내 네트워크

Alex는 Domestic Networks Inc.의 시스템 관리자입니다. 이 회사의 네트워크는 여러 건물에 걸쳐 아파트들을 연결하며, Alex는 새로운 구간을 설계해야 합니다.

Alex에게는 연결해야 할 아파트들과 그 사이에 놓을 수 있는 링크들이 표시된 지도가 있습니다. 각 링크는 두 아파트를 연결하며, 미터 단위의 길이가 정해져 있습니다. 목표는 모든 아파트가 (다른 아파트를 거쳐 간접적으로라도) 서로 연결되도록 만드는 것입니다.

회사는 가장 가까운 케이블 상점에서 케이블을 구입합니다. 이 상점은 카테고리 5와 카테고리 6 케이블만 판매하며, 가격은 각각 미터당 p5루블과 p6루블입니다. 상점에는 카테고리 5 케이블이 q5미터, 카테고리 6 케이블이 q6미터만 남아 있습니다.

건설 계획이란 실제로 설치할 링크들의 집합이며, 설치되는 각 링크는 카테고리 5 또는 카테고리 6 중 한 종류의 케이블 하나를 끊김 없이 이어 만듭니다. 계획의 비용은 사용한 모든 케이블 가격의 합입니다. 사용하는 카테고리 5 케이블의 총 길이는 q5를 초과할 수 없고, 카테고리 6 케이블의 총 길이는 q6를 초과할 수 없습니다.

모든 아파트를 연결하는 계획의 최소 비용을 구하세요.

첫째 줄에 두 정수 n과 m이 주어집니다. 각각 아파트의 수와 설치 가능한 링크의 수입니다 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000).

다음 m개의 줄에는 각 링크의 정보가 세 정수 a, b, l로 주어집니다. a와 b는 그 링크가 연결할 수 있는 두 아파트이고, l은 링크의 길이(미터)입니다 (1 ≤ a, b ≤ n, 0 ≤ l ≤ 100). 아파트는 1번부터 n번까지 번호가 매겨져 있습니다.

마지막 줄에는 네 정수 p5, q5, p6, q6가 주어집니다. 각각 카테고리 5와 카테고리 6 케이블의 미터당 가격과 보유 수량입니다 (1 ≤ p5, q5, p6, q6 ≤ 10000).

모든 아파트를 보유한 케이블로 연결할 수 있으면, 유효한 계획의 최소 총비용(루블)을 정수 하나로 출력합니다.

연결할 수 없으면 Impossible이라는 단어 하나만 출력합니다.