로미오와 줄리엣

문제

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

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

사건은 사람 $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$ 개 지워서 만들 수 있는, 줄리엣에게서 로미오에게로 가는 앙금의 최솟값을 소수점 아래 둘째 자리까지 반올림해 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.

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