Lemon Path

"난 벨만-포드보다 데이크스트라가 더 좋아... 근데 데이크스트라보다 BFS가 더 좋은데 어떡해?"

일반적으로, 간선에 가중치가 있는 무향 그래프에서 최단 경로는 간선 가중치의 합이 최소인 경로를 의미한다. 하지만 BFS를 너무 좋아하는 재원이는 경로에 포함된 간선의 개수를 최소화하고 싶다.

간선의 개수만 최소화하는 모든 경로를 레몬 경로라고 정의한다. 레몬 경로의 가중치는 해당 경로에 포함된 간선들의 가중치 합을 의미하며, 레몬 거리는 두 정점을 잇는 모든 레몬 경로에 대한 레몬 경로의 가중치의 평균을 의미한다.

정점이 $N$개이고, 양방향 간선이 $M$개 있는 연결 그래프가 주어진다. $i$번째 간선은 $U_i$와 $V_i$를 연결하며, 그 가중치는 $C_i$이다.

$1$번 정점과 다른 모든 정점 사이의 레몬 거리를 구하여라. 그래프에는 자기 자신으로 가는 간선이나 같은 두 정점을 잇는 여러 간선이 존재할 수 있다.

입력은 다음과 같은 형식으로 주어진다.

$N \ M$

$U_1 \ V_1 \ C_1$

$U_2 \ V_2 \ C_2$

$\vdots$

$U_M \ V_M \ C_M$

• $2 \le N \leq 100\ 000$.
• $1 \le M \leq 500\ 000$.
• $1 \leq U_i, V_i \leq N$ ($1 \leq i \leq M$).
• $0 \leq C_i < 998 \ 244 \ 353$ ($1 \leq i \leq M$).

첫째 줄부터 $N-1$개의 줄에 걸쳐 $i$번째 줄에 $1$번 정점과 $i+1$번 정점 사이의 레몬 거리를 다음과 같은 방법으로 출력한다.

레몬 경로의 길이가 $\dfrac{p}{q}$일 경우 $qm\equiv p \ (\mathrm{mod} \ 998 \ 244 \ 353)$, $0\le m<998 \ 244 \ 353$인 양의 정수 $m$을 출력한다. 단, $p$와 $q$는 서로소인 양의 정수이다. 또한 레몬 경로의 개수가 $998 \ 244 \ 353$의 배수인 경우가 주어지지 않음이 보장된다.

주어진 그래프를 그림으로 나타내면 다음과 같다. 각 정점에 대해 레몬 거리는 다음과 같이 계산된다.

\begin {itemize}

• $1$번 정점과 $2$번 정점 사이의 레몬 경로는 $(1, 2)$ 하나뿐이며, 레몬 거리는 $\dfrac{0}{1}=0$이다.
• $1$번 정점과 $3$번 정점 사이의 레몬 경로는 $(1, 3)$ 하나뿐이며, 레몬 거리는 $\dfrac{1}{1}=1$이다.
• $1$번 정점과 $4$번 정점 사이의 레몬 경로는 $(1, 2, 4)$와 $(1, 3, 4)$ 두 개가 있으며, 레몬 거리는 $\dfrac{2+5}{2}=\dfrac{7}{2}$이다.
• $1$번 정점과 $5$번 정점 사이의 레몬 경로는 $(1, 2, 5)$와 $(1, 3, 5)$ 두 개가 있으며, 레몬 거리는 $\dfrac{3+6}{2}=\dfrac{9}{2}$이다.

\end {itemize}

1. 그래프가 완전 그래프이다. 다시 말해, 임의의 서로 다른 두 정점을 잇는 간선이 정확히 하나씩 존재한다. (6점)
2. 모든 간선의 가중치가 $1$이다. (13점)
3. $N \le 10, M \le 20$. (16점)
4. $N \le 1\ 000, M \le 2\ 000$. (28점)
5. 추가적인 제약 조건이 없다. (37점)