타이밍

은하계의 충돌이 다가온다. MdI가 다스리는 은하계가 우리 은하를 무력으로 합병하려 한다. 우리 정보국은 적의 본부에 잠입해 병력 이동 계획을 통째로 알아냈다.

적의 병력은 $N$개의 요새에 나뉘어 주둔한다. 요새 $i$에 주둔한 병력의 힘의 통계값을 $u_i$라고 하자. 계획은 링크를 따라 병력을 옮기는 것이다. 링크 $(s, d, p)$는 매 시간 요새 $s$에 있는 병력 가운데 비율 $p$가 요새 $d$로 넘어간다는 뜻이다. 요새 사이를 오가는 시간은 무시한다.

한 시간 안에 일어나는 이동은 모두 그 시간이 시작될 때의 값을 기준으로 동시에 일어난다. 그래서 한 시간이 지나면 요새 $i$의 값은 다음과 같이 바뀐다.

$u_i' = u_i - \sum_{(s, d, p) \,:\, s = i} p \cdot u_i + \sum_{(s, d, p) \,:\, d = i} p \cdot u_s$

정부는 공격을 시작할 시각 $t$를 정했고, 적의 병력은 그때까지 계획대로 $t$시간 동안 움직인다. 적의 은하는 매우 멀어서 우리 함대가 도착하는 데 한 시간이 걸린다. MdI는 함대가 출발하는 순간 목표를 알아채고, 그곳에 닿을 수 있는 병력을 전부 즉시 움직인다. 이때는 링크의 방향을 무시하고 어느 쪽으로든 이동할 수 있으므로, 목표 요새 $v$와 링크로 이어진 요새는 병력을 하나도 남기지 않고 $v$로 보낸다.

따라서 함대가 도착한 순간 요새 $v$에 모이는 힘의 통계값 $g_v$는, $t$시간이 지난 시점의 $u_v$에 $v$와 링크로 이어진 요새의 값을 모두 더한 값이다. $A(v)$를 $v$와 링크 하나 이상으로 이어진 요새의 집합이라고 하면 (자기 자신은 넣지 않는다)

$g_v = u_v + \sum_{w \in A(v)} u_w$

이다. 링크 방향은 따지지 않고, 두 요새를 잇는 링크가 여러 개여도 그 요새의 값은 한 번만 더한다.

적의 은하에서 가장 약한 지점, 다시 말해 $g_v$가 가장 작은 요새의 값을 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 적의 요새의 수 $N$ ($1 \le N \le 100$), 링크의 수 $l$ ($0 \le l \le (N-1)^2$), 공격을 시작할 시각 $t$ ($0 \le t \le 5000$)가 주어진다. 둘째 줄에는 $N$개의 실수 $u_0, u_1, \dots, u_{N-1}$ ($0 \le u_i \le 1000$)이 주어진다. $u_i$는 요새 $i$에 주둔한 병력의 힘의 통계값이다.

이어지는 $l$개 줄에는 링크가 한 줄에 하나씩 주어진다. 각 줄은 정수 $s_j$ ($0 \le s_j < N$), 정수 $d_j$ ($0 \le d_j < N$), 실수 $p_j$ ($0 < p_j \le 1$)로 이루어지고, 매 시간 요새 $s_j$의 병력 가운데 비율 $p_j$가 요새 $d_j$로 이동한다는 뜻이다. 같은 쌍이 여러 번 나올 수 있고 $s_j = d_j$인 링크도 있을 수 있다. 한 요새에서 나가는 링크의 비율을 모두 더한 값은 1을 넘지 않는다.

각 테스트 케이스마다 적의 은하에서 가장 약한 지점의 값, 즉 함대가 도착했을 때 한 요새에 모이는 힘의 통계값 가운데 가장 작은 값을 한 줄에 하나씩 출력한다.

값은 소수점 아래 일곱째 자리에서 반올림해 소수점 아래 여섯 자리까지 출력한다. 예를 들어 정답이 $305$이면 305.000000을 출력한다. 입력은 정답이 반올림 경계에서 충분히 떨어지도록 주어지므로 반올림 방향이 갈리는 경우는 없다.

공격이 시작되는 순간에는 모든 링크를 양방향으로 쓸 수 있다. 목표 요새와 링크로 이어진 요새는 링크의 방향과 상관없이 병력 전부를 목표 요새로 보낸다.

그 앞의 $t$시간 동안 일어나는 이동은 계획대로 방향을 지킨다. 방향이 사라지는 것은 마지막 한 시간뿐이다.