트리의 재구성

시간 제한1초메모리 제한512 MB

요약

가중치 트리가 주어질 때, 각 질의마다 간선 하나를 추가하고 생긴 사이클에서 새 간선을 제외한 가장 무거운 간선을 제거한 뒤 두 정점 사이 거리를 출력한다.

문제

정점 $N$ 개로 이루어진 트리가 있다. 정점은 1번부터 $N$ 번까지 번호가 매겨져 있고, 트리의 간선은 양방향이며 각 간선마다 비용이 모두 다르다.

다음과 같은 쿼리를 수행하는 프로그램을 작성하여라.

u v w a b: $u$ 에서 $v$ 로 가는 비용이 $w$ 인 간선을 잇는다. 지웠을 때 트리가 되는 간선 중 새로 추가한 간선을 제외한 비용이 가장 큰 간선 하나를 지운다. 재구성된 트리의 $a$ 에서 $b$ 로 가는 경로의 비용을 출력한다.

각 쿼리가 끝나면 트리는 처음 상태로 돌아간다.

첫째 줄에 정점의 개수 $N$ 과 쿼리의 개수 $Q$ 가 주어진다. ( $2 \le N, Q \le 100,000$ )

둘째 줄부터 $N-1$ 개의 줄에 두 정점과 두 정점을 잇는 간선의 비용인 정수 $C$ 가 주어진다. ( $1 \le C \le 200,000$ )

다음 줄부터 각 쿼리의 $u, v, w, a, b$ 가 주어진다. ( $1 \le w \le 200,000$ , $u \ne v$ )

각 쿼리의 답을 출력한다.

예제 1

입력

10 5
1 3 3
3 2 7
4 1 9
1 6 2
6 8 4
8 9 10
3 5 5
5 7 8
10 5 1
10 8 6 7 9
2 5 13 2 3
1 9 11 1 9
5 1 12 10 2
3 5 17 5 4

예상 출력