부활절 연휴 스키 여행

스칸디나비아 사람들은 부활절 연휴에 큰 스키 리조트에서 스키를 즐긴다. 리조트에는 스키어를 위로 실어 나르는 리프트가 여러 개 있고, 아래로 내려가며 타는 다양한 난이도의 슬로프가 있다.

초보 스키어인 페르는 리프트를 무서워하지만 그래도 스키를 최대한 많이 타고 싶어 한다. 그는 다음 조건을 모두 만족하는 스키 여행을 계획하려고 한다.

• 어떤 리프트의 아래쪽 지점에서 출발하여 같은 지점으로 되돌아온다.
• 정확히 두 단계로 이루어진다. 먼저 리프트를 한 번 이상 타고 위로 올라가고, 그다음 슬로프만 타고 출발한 지점까지 내려온다.
• 가능한 한 덜 무섭다. 즉, (슬로프에서 스키를 탄 시간)과 (리프트를 타거나 기다린 시간)의 비율이 가능한 한 크다.

한 리조트에는 $n$개의 지점, $m$개의 슬로프, $k$개의 리프트가 있다 ($2 \le n \le 1000$, $1 \le m \le 1000$, $1 \le k \le 1000$). 각 슬로프는 더 높은 지점에서 더 낮은 지점으로 이어지고, 각 리프트는 더 낮은 지점에서 더 높은 지점으로 이어진다(리프트는 아래로 탈 수 없다). 각 리조트에는 유효한 스키 여행이 적어도 하나 존재함이 보장된다.

첫 번째 줄에는 처리할 리조트의 수가 주어진다. 각 리조트는 다음과 같이 주어진다. 첫 줄에 세 정수 $n$, $m$, $k$가 주어진다. 이어지는 $m$개의 줄에는 각 슬로프가 세 정수로 주어진다: 위쪽 지점, 아래쪽 지점(지점은 $1$부터 $n$까지 번호가 매겨진다), 그리고 그 슬로프를 내려가는 데 걸리는 시간(최대 $10000$). 그다음 $k$개의 줄에는 각 리프트가 세 정수로 주어진다: 아래쪽 지점, 위쪽 지점, 그리고 그 리프트를 기다렸다가 타고 올라가는 데 걸리는 시간(최대 $10000$). 두 지점을 잇는 리프트나 슬로프는 각각 최대 하나뿐이다.

각 리조트마다 한 줄에, 얻을 수 있는 가장 큰 무서움 비율을 기약분수 $p/q$ 형태로 출력한다. 이 비율은 (슬로프에서 보낸 총 시간)을 (리프트를 타거나 기다린 총 시간)으로 나눈 값이다.