로미오와 줄리엣

로미오와 줄리엣의 비극은 몬터규가와 캐퓰릿가의 오랜 반목에서 시작한다. 이 문제에서는 과거의 사건 몇 개를 지웠을 때 두 사람 사이의 앙금이 얼마나 줄어드는지를 계산한다.

오랜 반목이 남기는 앙금은 대개 연좌에서 온다. 누군가의 아들이거나 이모이거나 친구라는 이유만으로, 그 사람이 내 어머니나 사촌에게 저지른 잘못의 죄책감을 함께 짊어진다. 이를 사건과 관계로 모형화한다.

사건은 사람 $A$가 사람 $B$에게 나쁜 짓을 한 일이고, 피해량이 붙는다. $A$가 $B$를 살해했다면 피해량이 $100$, 사업에서 속였다면 $5$인 식이다. 과거에 일어난 모든 사건의 당사자와 피해량이 입력으로 주어진다.

관계는 한 사람의 죄책감과 아픔이 다른 사람에게 얼마나 옮겨가는지를 나타낸다. 관계 $(u, v, p)$는 $u$가 누군가에게 나쁜 짓을 했을 때 $v$가 $u$의 죄책감을 $p$의 비율만큼 물려받고, 누군가가 $u$에게 나쁜 짓을 했을 때 $v$가 $u$의 아픔을 $p$의 비율만큼 물려받는다는 뜻이다. $u$에서 $v$로 가는 비율과 $v$에서 $u$로 가는 비율은 서로 다를 수 있다.

죄책감과 아픔은 사람을 여러 번 거쳐 전달되고, 사슬을 따라가면서 비율이 곱해진다. $A$와 $B$가 친구이고 $B$와 $C$가 친구이며 두 우정이 각각 $0.5$를 전달하면 $C$는 $A$의 죄책감을 $0.25$의 비율만큼 물려받는다. 같은 두 사람을 잇는 사슬이 여러 개여도 앙금이 여러 번 쌓이지는 않는다. 곱이 가장 큰 사슬 하나만 센다.

사람 $1$은 언제나 줄리엣이고 사람 $2$는 언제나 로미오다. 사건 $(a, b, d)$가 줄리엣에게서 로미오에게로 옮기는 앙금은 $G(a) \times P(b) \times d$이다. $G(a)$는 $a$의 죄책감을 줄리엣에게 전달하는 사슬들의 비율 곱 중 가장 큰 값이고, $P(b)$는 $b$의 아픔을 로미오에게 전달하는 사슬들의 비율 곱 중 가장 큰 값이다. $a$가 줄리엣이면 $G(a) = 1$이고 $b$가 로미오면 $P(b) = 1$이다. 그런 사슬이 하나도 없으면 그 값은 $0$이다.

줄리엣에게서 로미오에게로 가는 전체 앙금은 남아 있는 모든 사건의 앙금을 더한 값이다. 줄리엣이 과거의 사건을 최대 $k$개까지 지울 수 있을 때, 전체 앙금의 최솟값을 구한다.

예를 들어 줄리엣의 사촌 티볼트가 로미오의 절친한 친구 머큐시오를 죽였고, 줄리엣의 아버지가 로미오의 아버지를 사업에서 속였다고 하자. 사촌은 양쪽으로 $0.4$, 절친한 친구는 양쪽으로 $0.8$, 아버지에서 자식으로는 $0.9$를 전달하며, 살해의 피해량은 $100$, 사업 사기의 피해량은 $5$다. 그러면 줄리엣에게서 로미오에게로 가는 앙금은 $0.4 \times 0.8 \times 100 + 0.9 \times 0.9 \times 5 = 36.05$다. 티볼트의 살해를 지우면 앙금은 $4.05$로 줄어든다. 머큐시오가 벤볼리오와도 친구이고 벤볼리오가 로미오와 친구여도 $0.4 \times 0.8 \times 0.8 \times 100$이 따로 더해지지는 않는다.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다. ($1 \le K \le 20$)

이어서 $K$개의 데이터 집합이 차례로 주어진다. 각 데이터 집합의 첫째 줄에는 네 정수 $n$, $r$, $m$, $k$가 공백으로 구분되어 주어진다. $n$은 등장인물 수로 $2 \le n \le 100$이고, 사람 $1$은 줄리엣, 사람 $2$는 로미오다. $r$은 관계의 개수로 $0 \le r \le n^2$이고, $m$은 과거에 일어난 나쁜 사건의 개수로 $0 \le m \le 10000$이며, $k$는 줄리엣이 지울 수 있는 사건의 최대 개수로 $0 \le k \le m$이다.

다음 $r$개의 줄에는 관계가 한 줄에 하나씩 $u_i$, $v_i$, $p_i$ 순서로 주어진다. $1 \le u_i, v_i \le n$이고, $p_i$는 $u_i$에서 $v_i$로 전달되는 비율로 $0 \le p_i \le 1$인 소수다. 같은 순서쌍 $(u_i, v_i)$가 두 번 나오지는 않지만, $(u_i, v_i)$와 $(v_i, u_i)$가 함께 나올 수는 있다.

다음 $m$개의 줄에는 나쁜 사건이 한 줄에 하나씩 $u_j$, $v_j$, $d_j$ 순서로 주어진다. $1 \le u_j, v_j \le n$이고, $d_j$는 $u_j$가 $v_j$에게 입힌 피해량으로 $0 \le d_j \le 10^4$인 소수다. 같은 순서쌍이 여러 번 나올 수 있다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 데이터 집합의 번호이고 $1$부터 시작한다. 다음 줄에 줄리엣이 사건을 최대 $k$개 지워서 만들 수 있는, 줄리엣에게서 로미오에게로 가는 앙금의 최솟값을 소수점 아래 둘째 자리까지 반올림해 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.

입력 자료는 정답이 소수 둘째 자리 두 값의 정확히 중간에 놓이지 않도록 만들어져 있어서, 반올림 결과가 하나로 정해진다.