Problem Description

To reduce the risk of cheating in programming contests, the school needs to assign $n$ contestants to $k$ computer labs for the contest.

It is known that some contestants are relatively familiar with each other. We use a weighted undirected graph $G=(V,E)$ to describe these relationships:

• Each vertex represents a contestant.
• Each edge represents that there is some relationship between two contestants.
• The edge weight is a positive integer indicating how close their relationship is. A larger weight means they are more familiar with each other.
• The graph $G$ is a simple graph with no self-loops and no multiple edges.

If the total relationship strength among contestants in the same lab is too high, it will increase the pressure on proctors.

For a certain lab, the sum of the weights of all edges whose both endpoints are assigned to this lab is called the risk value of this lab.

Let the sum of all edge weights in the whole graph be $S = \sum\limits_{e \in E} w_e$, where $w_e$ denotes the weight of edge $e$.

The school requires that the sum of the risk values of all labs must not exceed $\left\lceil \frac{S}{k} \right\rceil$.

Now you need to determine whether there exists an assignment such that:

• Each contestant is assigned to exactly one lab.
• The sum of the risk values of all labs does not exceed $\left\lceil \frac{S}{k} \right\rceil$.

If it exists, output one assignment that satisfies the requirements. If there are multiple valid assignments, output any one.

Note: It is allowed that a lab has no contestants assigned to it. The graph $G$ is not guaranteed to be connected.

Input Format

The first line contains three integers $n, m$ and $k$ ($1 \le k \le n \le 5\times 10^5, 0 \le m \le 5\times 10^5$), separated by spaces, representing the number of contestants, the number of relationships, and the number of computer labs.

The next $m$ lines each contain three integers $u, v$ and $w$ ($1 \le u,v \le n, u \ne v, 1 \le w \le 10^9$), separated by spaces, indicating an undirected edge of weight $w$ between contestant $u$ and contestant $v$.

It is guaranteed that there are no multiple edges in the input graph.

Output Format

If there is no assignment that satisfies the requirements, output one line containing only the string $\tt{No}$.

Otherwise output two lines:

• The first line contains the string $\tt{Yes}$.
• The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ($1 \le a_i \le k$), separated by spaces, where $a_i$ indicates that contestant $i$ is assigned to lab $a_i$.

If there are multiple valid assignments, output any one.

4 4 2
1 2 1
2 3 1
3 4 1
4 1 1

Yes
1 2 1 2 

Hint

Translated by ChatGPT 5