Problem Statement

Given is an undirected connected graph with $N$ vertices numbered $1$ to $N$, and $M$ edges numbered $1$ to $M$. The given graph may contain multi-edges but not self loops.

Each edge has an integer label between $1$ and $N$ (inclusive). Edge $i$ has a label $c_i$, and it connects Vertex $u_i$ and $v_i$ bidirectionally.

Snuke will write an integer between $1$ and $N$ (inclusive) on each vertex (multiple vertices may have the same integer written on them) and then keep only the edges satisfying the condition below, removing the other edges.

Condition: Let $x$ and $y$ be the integers written on the vertices that are the endpoints of the edge. Exactly one of $x$ and $y$ equals the label of the edge.

We call a way of writing integers on the vertices good if (and only if) the graph is still connected after removing the edges not satisfying the condition above. Determine whether a good way of writing integers exists, and present one such way if it exists.

Constraints

• $2 \leq N \leq 10^5$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq u_i,v_i,c_i \leq N$
• The given graph is connected and has no self-loops.

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1 c_1
\vdots
u_M v_M c_M

Output

If there is no good way of writing integers, print No. Otherwise, print $N$ lines. The $i$-th line should contain the integer written on Vertex $i$. Any good way of writing integers will be accepted.