도시 지도

피넛은 휴가를 위해 도시 실버밀로 떠난다. 그래서 실버밀의 지도가 필요하다. 하지만 그의 컴퓨터가 고장 나서 인터넷으로 지도를 찾을 수 없다.

실버밀에는 교차로 $N$개가 있고, 1번부터 $N$번까지 번호가 매겨져 있다. 도로는 $N-1$개이다. 도로 $i$는 교차로 $A_i$와 $B_i$를 양방향으로 잇고, 어느 방향으로 지나든 $W_i$분이 걸린다. 도시는 완전히 연결되어 있어서, 도로를 따라 어떤 교차로에서든 다른 교차로로 갈 수 있다. 교통 체증을 막기 위해 실버밀의 주지사는 어떤 교차로에도 연결된 도로가 세 개를 넘지 않도록 정했다.

피넛은 실버밀의 지도를 얻어야 한다. 즉, $i = 1, \ldots, N-1$에 대해 $(A_i, B_i, W_i)$를 알아내야 한다.

피넛은 실버밀의 측량사를 고용했다. 측량사는 실력이 그리 좋지 않고, 한 가지 종류의 질문에만 답할 수 있다. 교차로 $X$에서 교차로 $Y$까지 이동하는 데 필요한 최소 시간(분)이 얼마인지 묻는 질문이다. 측량사는 $Q$번만 답한 뒤 일을 그만둔다.

피넛이 실버밀의 지도를 그릴 수 있도록 질문 목록을 설계해 달라. 도와줄 수 있겠는가?

• $2 \le N \le 1000$
• $1 \le A_i, B_i \le N$
• $1 \le W_i \le 10^9$