34539번 - Konpaku Youmu

문제

요우무는 반인반령(반쪽은 사람, 다른 반쪽은 유령)이다. 요우무의 반령은 보통 요우무의 지시에 따라서 움직이지만, 원한다면 자신의 의지로 움직이는 것도 가능하다.

요우무는 잠시 산책을 나와 인간 세상을 둘러보려고 한다. 인간 세상은 $N$개의 마을로 나뉘며, 두 마을을 잇는 양방향 도로가 $N-1$개 존재한다. 마을은 1ドル$번부터 $N$번까지 번호가 매겨져 있고, 각 도로는 길이를 가진다. 모든 마을은 도로를 통해서 서로 오갈 수 있다.

요우무와 요우무의 반령은 각자 따로 산책하며, 산책하는 도중에 가끔씩 요우무가 반령과 자신의 거리가 너무 떨어져 있다고 생각하면 반령을 불러 자신과의 거리가 $K$ 이내인 마을에 오도록 지시한다. 단, 길에서는 연락할 수단이 전혀 없기 때문에 요우무가 반령을 부르기 위해서는 요우무와 반령 모두 마을에 위치해 있어야 하며, 반령은 요우무의 지시를 따르되 최단 거리로 움직인다. 이미 요우무와 반령의 거리가 $K$ 이내라면 반령은 움직이지 않는다.

요우무가 마을 $u$에 있고 반령이 마을 $v$에 있을 때, 요우무가 반령에게 지시를 내린 뒤의 요우무와 반령 사이의 최단 거리를 $dist_K(u,v)$라고 하자. $dist_K(u,u)$는 0ドル$으로 정의한다. 여러분이 할 일은 모든 $(u,v)$ 쌍에 대해서 $dist_K(u,v)$의 합을 구하는 것이다. 식으로 표현하면 다음과 같다.

\[\sum^{N}_{u=1}\sum^{N}_{v=1}dist_K(u,v)\]

단, 답이 너무 클 수 있으므로 998ドル,円 244,円 353$으로 나눈 나머지를 구한다.

입력

첫째 줄에 $N$과 $K$가 주어진다 $(2\le N\le 100,円 000; 1\le K\le 10^{10})$

둘째 줄부터 $N-1$개의 줄에 걸쳐 세 정수 $u,ドル $v,ドル $c$가 공백으로 구분되어 주어진다. 이는 두 마을 $u$와 $v$를 잇는 길이가 $c$인 양방향 도로가 존재한다는 의미다. $(1\le u,v\le N, u \ne v; 1\le c\le 100,円 000)$

모든 마을은 도로를 통해서 서로 오갈 수 있음이 보장된다.

출력

주어진 수식의 계산 결과를 998ドル,円 244,円 353$으로 나눈 나머지를 출력한다.

제한

힌트