N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 번호가 붙어 있다.

j (\(1 \le j \le M\))번 간선은 \(a_{j}\)번 정점과 \(b_{j}\)번 정점을 연결하며, 정수 가중치 \(c_{j}\)가 붙어 있다.

당신은 모든 정점에 정수 가중치를 부여해야 한다. i (\(1 \le i \le N\))번 정점에 부여할 가중치를 \(x_{i}\)라고 하자.

정점에 가중치를 부여하는 총 비용은 각 정점의 가중치의 절댓값의 합, 즉 \(|x_{1}| + |x_{2}| + \cdots + |x_{N}|\)과 같다.

그래프의 균형이 맞으려면, 각 간선이 연결하고 있는 두 정점의 가중치의 합이 간선의 가중치와 같아야 한다. 즉, 모든 j (\(1 \le j \le M\))에 대해, x_{\(a_{j}\)} + x_{\(b_{j}\)}이 \(c_{j}\)와 같아야 한다.

예를 들어, 아래와 같이 5개의 정점과 4개의 간선으로 이루어진 그래프를 생각하자. 그림에서 정점을 나타 내는 원 안에 적힌 수는 정점의 번호이고, 간선을 나타내는 선에 적힌 수는 간선에 붙은 가중치이다.

아래의 그림과 같이 각 정점에 [2, -7, 3, -5, 0]의 가중치를 부여해서, 각 간선이 연결하고 있는 두 정점의 가중치의 합이 간선의 가중치와 같게 할 수 있다. 아래 그림에서 정점을 나타내는 원 안에 적힌 수는 정점의 가중치이다.

총 비용은 |2| + | − 7| + |3| + | − 5| + |0| = 2 + 7 + 3 + 5 + \(0 = 17\)이다. 총 비용을 17보다 작게 할 수 있는 방법은 없기 때문에, 위 방법은 총 비용을 최소화하는 방법이다.

아래와 같이 각 정점에 [6, -3, -1, -9, 4]의 가중치를 부여해도 균형이 맞는 그래프가 되지만, 이 경우 총 비용은 17보다 큰 23이 되기 때문에 아래 방법은 총 비용을 최소화하는 방법이 아니다.

그래프의 균형이 맞도록 정점에 가중치를 부여하는 것이 가능한지 확인하고, 가능하다면 그 중 총 비용을 최소화하는 방법을 하나 구하는 프로그램을 작성하라.

Hint.

|x|는 x < 0이면 −x, \(x \ge 0\)이면 x인 절댓값 기호이다.

참고: \(|x|\)는 \(x < 0\)이면 \(-x\), \(x \ge 0\)이면 \(x\)인 절댓값 기호이다.

• 주어지는 모든 수는 정수이다.
• \(2 \le N \le 100\,000\)
• \(1 \le M \le 200\,000\)
• 모든 \(j\) (\(1 \le j \le M\)) 에 대해:
• \(1 \le a_j \le N\), \(1 \le b_j \le N\)
• \(a_j \ne b_j\). 즉, 서로 같은 두 정점을 연결하는 간선은 없다.
• \(-1\,000\,000 \le c_j \le 1\,000\,000\)
• 모든 \(j, k\) (\(1 \le j < k \le M\)) 에 대해, \(\{a_j, b_j\} \ne \{a_k, b_k\}\). 즉, 서로 다른 두 정점 쌍 \((a, b)\) 를 잇는 간선은 많아야 한 개 존재한다.
• 그래프는 연결 그래프이다. 즉, 그래프에서 어떤 두 정점을 골라도, 간선들을 통해 두 정점을 직, 간접적으로 잇는 경로가 존재한다.

첫째 줄에 N과 M이 순서대로 공백을 사이에 두고 주어진다.

다음 M개의 줄에 각 간선에 대한 정보가 주어진다. 이 중 j (\(1 \le j \le M\))번째 줄에는 세 정수 \(a_{j},b_{j},c_{j}\)가 공백 하나씩을 사이로 두고 주어진다.

만약 그래프의 균형이 맞도록 정점에 정수 가중치를 부여하는 방법이 존재한다면:

• 첫째 줄에 Yes를 출력한다. 출력은 대소문자를 구분하지 않는다.
• 둘째 줄에 각 정점에 부여한 가중치를 나타내는 N개의 정수 \(x_{1},x_{2}\), . . ., \(x_{N}\)을 공백 하나씩 사이에 두고 출력한다. 그래프의 균형이 맞도록 하면서 총 비용을 최소화하는 방법이 여럿 존재한다면, 그러한 방법들 가운데 어떤 것을 출력해도 된다.

만약 그래프의 균형이 맞도록 정점에 정수 가중치를 부여하는 방법이 존재하지 않는다면:

• 첫째 줄에 No를 출력한다. 출력은 대소문자를 구분하지 않는다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2021 > 2차 대회 > 초등부 4번 / 고등부 2번