선인장 접기 Plus

이 문제는 "선인장 접기"의 어려운 버전입니다. 두 버전은 $l$에 대한 제약이 다르며, 어려운 버전에서는 대응되는 $x_i$의 값을 직접 출력해야 합니다.

선인장 그래프는 모든 간선이 최대 하나의 단순 사이클에만 포함된 무향 그래프입니다. 흐즈로는 선인장 그래프를 하나 갖고 있으며, 각 간선에는 길이가 있습니다. 두 정점 $u$, $v$를 잇고 길이가 $l$인 간선은 순서쌍 $(u, v, l)$로 나타냅니다. 흐즈로는 자신의 그래프를 보다가 이런 생각을 했습니다.

• 어떤 선인장 그래프는 적당히 접어서 1차원으로 만들 수도 있지 않을까?

이 의문을 풀기 전에, 다음 성질을 만족하는 그래프를 접어서 1차원으로 만들 수 있다고 정의합시다.

• 각 정점 $i$에 1차원 좌표 $x_i$를 배정하여, 각 간선 $(u, v, l)$에 대해 $|x_u - x_v| = l$이 성립하도록 할 수 있다.

입력으로 주어지는 선인장 그래프를 접어서 1차원으로 만들 수 있는지 판단하세요.

첫 번째 줄에 그래프의 정점 개수 $n$과 간선 개수 $m$이 공백으로 구분되어 주어집니다. ($1 \le n \le 10^5$, $0 \le m \le \min(\lfloor 1.5(n-1) \rfloor, 10^5)$)

두 번째 줄부터 $m$개의 줄에 간선 정보가 한 줄에 하나씩 주어집니다. $i$번째 줄에는 $i$번째 간선이 잇는 두 정점 $u_i$, $v_i$와 간선의 길이 $l_i$가 공백으로 구분되어 주어집니다. ($1 \le u_i, v_i \le n$, $u \ne v$, $0 \le l_i \le 500$)

주어진 그래프에는 중복 간선이나 자기 자신을 향하는 간선이 없으며, 선인장 그래프임이 보장됩니다.

그래프를 접어서 1차원으로 만들 수 있다면 첫 번째 줄에 YES를 출력하세요.

그다음 줄에는 $n$개의 정수 $x_1, x_2, \cdots, x_n$을 공백으로 구분하여 출력하세요. $i$번째 정수는 $i$번째 정점의 좌표이며, $[-10^9, 10^9]$ 구간 안에 있어야 합니다. 모든 간선 $(u, v, l)$에 대해 $|x_u - x_v| = l$이 성립하면 그 출력을 정답으로 인정합니다. 이 문제의 제약 아래에서 그래프를 접어서 1차원으로 만들 수 있다면, 모든 간선의 조건을 만족하는 $[-10^9, 10^9]$ 구간의 정수 배정이 항상 존재함을 증명할 수 있습니다.

그래프를 접어서 1차원으로 만들 수 없다면 한 줄에 NO를 출력하세요.

이 문제에서 정의하는 선인장 그래프는 연결 그래프가 아닐 수 있음에 주의하세요.