국제 옥토끼 기구

문제

달에 사는 곰인 옥토끼2는 국제 옥토끼 기구(IMO, International moonrabbit organization) 회의 장소 예약부의 과장이다. 지금까지 N개 국가가 달에 진출하여 기지를 하나씩 만들었다고 한다. 국가들은 1번부터 N번까지의 번호가 붙어있다. 곰들은 달에서 무역하기 위해서 두 기지 사이를 연결하는 양방향 도로를 만들었다. 양방향 도로는 비용 절감을 위해 N-1개만을 만들었고, 이 도로들만 이용해도 임의의 두 기지 사이를 이동할 수 있다고 한다. 도로는 1번부터 N-1번까지 번호가 붙어있다. i번 도로는 $S_{i}$번 국가의 기지와 $E_{i}$번 국가의 기지를 연결하며, 걸어서 이동하는데 $D_{i}$초가 걸린다.

2020년 1월 1일, 국제 옥토끼 기구 탄생 100주년을 기념하여 1년간 매일 회의를 열기로 하였다. 2020년은 총 Q일이며, i번째 날의 회의는 $V_{i}$번 국가의 기지에서 열리고, $L_{i}$ ~ $R_{i}$번 국가의 기지들에서 각각 한 마리씩 참여한다. 옥토끼2는 회의 장소를 예약하기 위해 i번째 날의 회의에 곰들이 도착하는 시간이 날이 시작되고 몇 초 후인지를 알아야 한다. 모든 곰은 부지런하여 날이 시작되는 즉시 출발하여 회의 장소까지 최단 시간으로 걸어오고, 회의가 끝나면 즉시 원래 있던 기지로 돌아간다. 회의가 열리는 날마다 옥토끼2에게 회의 장소에 가장 일찍 도착하는 곰이 도착하는 시간, 가장 늦게 도착하는 곰이 도착하는 시간, 모든 곰이 도착하는 시간의 평균을 알려주자.

입력

첫째 줄에 N, Q가 주어진다. (1 ≤ N, Q ≤ $10^{5}$)

다음 N-1줄 중 i번째 줄에는 i번 도로의 정보 $S_{i}$, $E_{i}$, $D_{i}$가 주어진다. (1 ≤ $S_{i}$, $E_{i}$ ≤ N, 1 ≤ $D_{i}$ ≤ $10^{8}$)

주어진 도로들만 이용해서 임의의 두 기지 사이를 이동할 수 있음이 보장된다.

다음 Q줄 중 i번째 줄에는 i번째 날의 회의에 대한 정보 $L_{i}$, $R_{i}$, $V_{i}$가 주어진다. (1 ≤ $L_{i}$ ≤ $R_{i}$ ≤ N, 1 ≤ $V_{i}$ ≤ N)

출력

i번째 날의 회의에서 가장 일찍 도착하는 곰이 도착하는 시간을 $\min_i$초, 가장 늦게 도착하는 곰이 도착하는 시간을 $\max_i$초, 회의에 참석하는 모든 곰이 도착하는 시간의 합을 $\text{sum}_i$초라고 할 때, i번째 줄에 $\min_i$, $\max_i$, $\text{sum}_i$을 출력한다.

4 5
4 3 34
1 2 13
2 4 56
1 4 1
1 3 3
1 4 4
1 2 3
3 4 1

0 103 185
0 103 193
0 69 159
90 103 193
69 103 172

10 10
10 1 54
2 5 23
4 10 2
2 8 100
6 3 44
7 6 35
9 5 18
10 5 100
5 3 72
2 7 2
4 10 1
1 1 2
1 10 2
1 5 9
1 3 8
1 8 9
6 7 2
1 6 7
8 8 7

0 174 556
54 305 1288
177 177 177
0 177 997
18 172 441
100 277 572
18 172 885
139 174 313
35 305 997
274 274 274

출처

• 문제를 만든 사람: imeimi2000