무임승차

상현이는 어떤 기밀 단체의 요원이고, 매일 아침 기차를 타고 출근한다. 어느 날 상현이는 뭔가 불합리하다는 것을 알아챘다. 자기는 매일 꼬박꼬박 요금을 내고 타는데, 정작 승무원이 티켓을 확인하는 일은 드물었기 때문이다. 몇 년에 걸쳐 상현이는 선로마다 티켓을 확인받을 확률이 얼마인지 모두 기록해 두었다.

무임승차 벌금은 보통 실제 요금보다 비싸다. 그래서 상현이는 모든 구간에서 요금을 내지 않는 대신, 요금과 벌금과 확인받을 확률을 계산해서 기댓값이 가장 작은 방법으로 출근하기로 했다. 어떤 구간에서는 요금을 내고 타는 편이 낫고, 어떤 구간에서는 무임승차가 나을 것이다.

티켓은 출발지 A와 도착지 B를 정해서 산다. 가격은 기본 요금 $s$원에 A와 B 사이 최단거리 1킬로미터당 $p$원을 더한 $s + p \times \mathrm{dist}(A, B)$원이다. 여기서 $\mathrm{dist}(A, B)$는 두 도시 사이의 최단거리다. 이 티켓으로는 A와 B 사이를 최단거리로 운행하는 기차만 탈 수 있다.

티켓 없이 탄 기차에서 확인을 받으면 벌금을 낸다. 벌금은 기본 $y$원에, 지금 탄 기차가 마지막으로 들른 도시부터 이번 정차역까지의 거리 1킬로미터당 $p$원을 더한 값이다. 원래 무임승차가 적발되면 기차에서 바로 내려야 하지만, 상현이는 기밀 요원이라 변장에 능하다. 적발되어도 벌금을 낸 뒤 계속 기차를 탈 수 있다.

start에서 end까지 출근할 때 요금의 기댓값이 가장 작아지는 경로를 찾아, 그 기댓값을 구하는 프로그램을 작성하시오.

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

각 테스트 케이스는 다음과 같이 구성된다.

• 첫 줄에 공백으로 구분된 정수 7개가 주어진다.

  1. $n$ ($2 \le n \le 200$): 기차의 운행 경로에 놓인 도시의 수
  2. $m$ ($1 \le m \le n(n-1)/2$): 두 도시를 직접 잇는 선로의 수
  3. $\mathrm{start}$ ($1 \le \mathrm{start} \le n$): 출발지
  4. $\mathrm{end}$ ($1 \le \mathrm{end} \le n$, $\mathrm{start} \ne \mathrm{end}$): 도착지
  5. $s$ ($1 \le s \le 1000$): 티켓의 기본 요금
  6. $p$ ($1 \le p \le 1000$): 티켓과 벌금에 붙는 1킬로미터당 추가 요금
  7. $y$ ($s < y \le 1000$): 무임승차 벌금의 기본 요금

• 다음 $m$개의 줄에는 선로 하나의 정보가 공백으로 구분된 정수 4개로 주어진다. 모든 선로는 양방향이다. $i$번째 줄의 데이터는 다음과 같다.

  1. $a_i$ ($1 \le a_i \le n$): $i$번째 선로의 한쪽 끝 도시 번호
  2. $b_i$ ($a_i < b_i \le n$): $i$번째 선로의 다른 쪽 끝 도시 번호
  3. $c_i$ ($0 \le c_i \le 100$): $i$번째 선로를 운행하는 기차에서 티켓을 확인받을 확률(퍼센트 값으로 주어진다)
  4. $d_i$ ($1 \le d_i \le 1000$): $i$번째 선로의 길이(단위는 킬로미터)

$i \ne j$인 모든 쌍에 대해 $(a_i, b_i) \ne (a_j, b_j)$다. 즉 같은 두 도시를 잇는 선로가 두 번 주어지지는 않는다. start에서 end까지 가는 경로는 항상 존재한다.

각 테스트 케이스마다 start에서 end까지 가는 데 드는 요금의 기댓값의 최솟값을 한 줄에 하나씩 출력한다. 소수점 아래 둘째 자리까지 출력하고, 끝자리가 0이더라도 두 자리를 모두 적는다.

요금과 벌금의 기댓값은 모두 0.01원 단위로 딱 떨어지므로, 반올림이 애매해지는 경우는 생기지 않는다.

벌금의 기댓값은 확인받을 확률과 벌금을 곱한 값이다. 선로마다 확인 여부가 독립이므로, 경로 X에서의 기댓값을 $E[X]$, 경로 Y에서의 기댓값을 $E[Y]$라 하면 X와 Y를 이어 붙인 경로의 기댓값은 $E[X] + E[Y]$다.

공개 테스트에 담긴 세 번째 데이터에서, 도시 1부터 도시 4까지 가는 최적의 경로는 이렇다. 도시 1에서 도시 2까지는 요금 20원을 내고 티켓을 사고($10 + 1 \times 10$), 도시 2에서 도시 3까지는 무임승차하고(이때 벌금의 기댓값은 $0.1 \times (100 + 1 \times 120) = 22$원), 도시 3에서 도시 4까지는 다시 요금 20원을 내고 티켓을 산다($10 + 1 \times 10$). 이렇게 출근하면 요금의 기댓값이 $20 + 22 + 20 = 62$원이고, 이보다 작게 만들 수는 없다.