트리와 쿼리 2

N개의 정점으로 이루어진 트리가 있다. 트리는 사이클이 없는 무방향 연결 그래프이다. 정점에는 1번부터 N번까지 번호가 매겨져 있고, 간선에는 1번부터 N-1번까지 번호가 매겨져 있다.

트리에서 두 정점을 잇는 경로는 하나뿐이다. 아래 두 쿼리를 처리하는 프로그램을 작성하시오.

• 1 u v: u에서 v로 가는 경로의 비용을 출력한다. 경로의 비용은 그 경로에 포함된 간선의 비용을 모두 더한 값이다.
• 2 u v k: u에서 v로 가는 경로에 있는 정점 중 k번째 정점을 출력한다. u가 1번째 정점이고 v가 마지막 정점이다.

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N-1개 줄에는 i번 간선이 잇는 두 정점 번호 u와 v, 그리고 간선의 비용 w가 주어진다. w는 1,000,000 이하의 자연수이다.

다음 줄에 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개 줄에는 쿼리가 한 줄에 하나씩 주어진다. 2번 쿼리의 k는 u에서 v로 가는 경로에 포함된 정점의 수보다 작거나 같은 자연수이다.

각 쿼리의 결과를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.