경찰과 도둑

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

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

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

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

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

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

• $2 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• 모든 $0 \le i \le N - 2$에 대해 $0 \le A[i], B[i] \le N - 1$이고 $A[i] \ne B[i]$이다.
• 모든 $0 \le i \le N - 2$에 대해 $1 \le D[i] \le 1\,000\,000$이다.
• KOI 마을은 트리 구조를 이룬다.
• 모든 $0 \le j \le Q - 1$에 대해 $0 \le P[j], T[j] \le N - 1$이고 $P[j] \ne T[j]$이다.
• 모든 $0 \le j \le Q - 1$에 대해 $1 \le V1[j], V2[j] \le 1\,000\,000$이다.