플러버와 물 배관망

2년 전, 당신은 고향에 전국 최초의 플러버 배관망을 까는 일을 도왔다. 지금은 집집마다 부엌에 플러버 공급구가 있다. 최근 누군가 플러버를 물과 섞으면 불을 끌 수 있다는 사실을 발견했다. 요즘 화재가 잦아서 쓸모가 큰 발견이다.

시의회는 도시 한가운데에 플러버 소방서(FD)를 두고 그곳에서 플러버와 물의 혼합액을 만들기로 했다. FD의 훈련받은 직원이 처리한 플러버를 화재 현장으로 옮긴다.

배관은 이미 깔려 있다. 배치가 주어지면 플러버 공장의 플러버와 수원의 물을 배관으로 FD까지 보내는 방법을 정해야 한다.

두 액체는 같은 배관망을 흐르고, 같은 관을 함께 흐르기도 한다. 모든 관은 양방향이지만 한 관에서 플러버와 물이 서로 반대 방향으로 흐를 수는 없다. 같은 방향으로 흘려보내면 반드시 섞이므로, 각 지점에는 막과 필터가 있어서 들어온 혼합액을 원하는 대로 분리하고 다시 나눌 수 있다. 배관망은 닫힌 계라서, 어떤 액체의 공급원과 FD를 제외한 모든 지점에서 그 액체가 들어오는 유량과 나가는 유량이 같다.

관마다 용량이 정해져 있다. 플러버는 점성이 $v$라서, 물을 초당 $v$리터 보낼 수 있는 관으로 플러버는 초당 1리터만 보낼 수 있다. 혼합액에 대해서는 용량이 선형으로 변한다. 관의 물 용량을 $c$, 그 관을 흐르는 플러버와 물의 유량을 각각 $f$와 $w$(단위는 초당 리터)라고 하면 $v \cdot f + w \le c$를 만족해야 한다.

FD에 도착하는 혼합액에는 물이 충분히 있어야 하고(희석하지 않은 플러버는 불이 잘 붙는다), 플러버도 충분히 있어야 한다(플러버 없는 플러버 소방서는 의미가 없다). 최종 혼합액의 가치는 $F^a W^{1-a}$로 정한다. $F$는 FD에 도착하는 플러버의 유량, $W$는 도착하는 물의 유량이고, $a$는 0과 1 사이의 주어진 상수다.

달성할 수 있는 $F^a W^{1-a}$의 최댓값을 구하라.

첫째 줄에 지점의 수 $n$ ($3 \le n \le 200$), 관의 수 $p$ ($n - 1 \le p \le n(n-1)/2$), 실수 $v$ ($1 \le v \le 10$)와 $a$ ($0.01 \le a \le 0.99$)가 주어진다. 지점 번호는 1번부터 $n$번까지이고, 1번은 플러버 공장, 2번은 수원, 3번은 FD다. 실수의 소수점 아래 자릿수는 10자리 이하다.

다음 $p$개 줄에 관이 하나씩 주어진다. 각 줄에는 관이 잇는 두 지점을 나타내는 정수 $j$와 $k$ ($1 \le j < k \le n$), 그리고 초당 리터 단위의 물 용량을 나타내는 정수 $c$ ($1 \le c \le 10$)가 주어진다.

같은 지점 쌍을 잇는 관은 두 개 이상 없으며, 배관망은 연결되어 있다.

달성할 수 있는 $F^a W^{1-a}$의 최댓값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 관별 유량은 출력하지 않는다.