34153번 - Unravel the Graph 서브태스크스페셜 저지

문제

우정이와 구름이는 양의 가중치가 부여된 무향 연결 그래프 $G$를 하나 마주하였다!

그래프는 $N$개의 정점과 $M$개의 간선으로 구성되어 있으며, 각 간선 $(u_i, ,円 v_i, ,円 c_i)$에 대해 정점 $u_i$와 $v_i$ 사이를 방향 없이 잇고, 그 가중치가 $c_i$이다.

우정이는 그래프의 각 정점을 수직선 상에 배치하여 펼치는 작업을 진행한다. 이때, 그래프의 각 정점 $v$를 정수 위치 $x(v)$에 배치하되, 어느 두 정점 $u_i, v_i$를 잇는 간선의 가중치를 넘어서는 간격이 발생해서는 안 된다. 즉, 모든 간선 $(u_i, ,円 v_i, ,円 c_i)$에 대해 $|x(u_i) - x(v_i)| \leq c_i$가 되어야 한다.

이렇게 펼친 뒤 폭을 다음과 같이 정의한다: 수직선 상에서 서로 가장 멀리 떨어진 두 정점의 떨어진 거리, 다시 말해 $\displaystyle \max_{1 \leq i < j \leq N} |x(i) - x(j)|$이다.

구름이는 폭을 최대화하고 싶었기에, 우정이에게 가능한 폭 중 가장 큰 값을 가지는 펼치기를 요구했다.

"이 그래프, 어떻게 해야 폭을 가장 넓게 펼칠 수 있을까? 가르쳐줘, 그 구조를!"

우정이를 대신하여 모든 펼치기 방법 중 이 폭이 최대가 되게 $x(1), x(2), \cdots, x(N)$을 정해보자!

입력

첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. (2ドル \leq N \leq 500,ドル $N-1 \leq M \leq 200,000$)

그래프는 연결 그래프임이 보장되며, 동일한 정점 쌍을 연결하는 간선이 여러 개 존재할 수 있다.

두 번째 줄부터 $M$개의 줄에 걸쳐 $i$번째 줄에 $i$번째 간선의 정보 $u_i,ドル $v_i,ドル $c_i$가 공백으로 구분되어 주어진다. (1ドル \le u_i, v_i \le N,ドル $u_i \neq v_i,ドル 1ドル \le c_i \le 10^9$)

출력

첫 번째 줄에 모든 펼치기 방법 중 폭이 최대가 되는 $x(1), x(2), \cdots, x(N)$을 공백으로 구분하여 출력하라. 각 $x(i)$는 정수이며, $-10^{18} \leq x(i) \leq 10^{18}$ 이어야 한다.

제한

서브태스크

힌트