경찰과 도둑

KOI 마을은 $N$개의 집과 집들을 잇는 $N - 1$개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 집들을 도로만을 사용하여 오갈 수 있다. 즉, KOI 마을의 도로망은 트리 구조를 이룬다.

KOI 마을의 집들에는 $0$부터 $N − 1$까지의 서로 다른 번호가 붙어 있으며, KOI 마을의 도로들에는 $0$부터 $N - 2$까지의 서로 다른 번호가 붙어 있다. 모든 $0 ≤ i ≤ N - 2$에 대해 $i$번 도로는 $A[i]$번 집과 $B[i]$번 집을 연결하며 길이는 $D[i]$미터이다.

최근 KOI 마을에 도둑이 자주 들어 주민들이 어려움을 겪고 있다. 이에 KOI 마을의 한 집에 경찰을 대기시켜, 도둑이 나타났을 때를 대비하려고 한다. KOI 마을의 사람들은 도둑이 드는 상황에서 경찰이 얼마나 빠르게 도둑을 잡을 수 있을지 궁금해졌다.

여러분에게 $Q$개의 시나리오가 주어진다. 시나리오에는 $0$부터 $Q - 1$까지의 서로 다른 번호가 붙어 있다. 하나의 시나리오는 다음과 같이 이루어진다.

$j$번 시나리오에서 경찰은 $P[j]$번 집에서 출발하며 $1$초에 최대 $V1[j]$미터를 이동할 수 있다.
$j$번 시나리오에서 도둑은 $T[j]$번 집에서 출발하며 $1$초에 최대 $V2[j]$미터를 이동할 수 있다.
경찰이 출발하는 집과 도둑이 출발하는 집은 다르다. 즉, $P[j] \ne T[j]$이다.
집의 크기는 충분히 작으므로 집은 점으로 취급한다. 도로의 너비는 충분히 좁으므로 도로는 선분으로 취급한다. 도로들은 교차하지 않는다.
경찰과 도둑은 각각 자신의 최대 속력 내에서 KOI 마을 안을 자유롭게 이동할 수 있다. 이동하지 않는 것도 가능하다.
경찰이 도둑과 같은 위치에 있다면 경찰은 도둑을 잡을 수 있다. 이때, 집뿐만이 아니라 도로의 중간에서도 도둑을 잡는 것이 가능하다.
시나리오 내에서 경찰과 도둑은 자신과 상대방의 속도를 알고 있으며, 어느 시점이든 상대방의 위치를 알 수 있다.
경찰과 도둑은 최선의 전략을 사용한다. 즉, 경찰은 도둑을 가장 빠르게 잡는 전략을, 도둑은 가장 오랫동안 도망치는 전략을 사용한다. 경찰과 도둑이 최선의 전략을 사용할 때, 반드시 유한한 시간 안에 도둑이 잡힘을 증명할 수 있다.

여러분은 각 시나리오마다 도둑이 잡히는 데에 걸리는 시간을 구해야 한다.

경찰과 도둑

문제

제한