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.

-----Sample Input-----
3 4
1 2 1
2 3 2
3 1 3
1 3 1

-----Sample Output-----
1
2
1

 - We write 1, 2, and 1 on Vertex 1, 2, and 3, respectively.
 - Edge 1 connects Vertex 1 and 2, and its label is 1.
 - Only the integer written on Vertex 1 equals the label, so this edge will not get removed.
 - Edge 2 connects Vertex 2 and 3, and its label is 2.
 - Only the integer written on Vertex 2 equals the label, so this edge will not be removed.
 - Edge 3 connects Vertex 1 and 3, and its label is 3.
 - Both integers written on the vertices differ from the label, so this edge will be removed.
 - Edge 4 connects Vertex 1 and 3, and its label is 1.
 - Both integers written on the vertices equal the label, so this edge will be removed.
 - After Edge 3 and 4 are removed, the graph will still be connected, so this is a good way of writing integers.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
import sys
sys.setrecursionlimit(10 ** 6)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
(n, m) = map(int, input().split())
ans = [-1] * n
uf = UnionFind(n)
g = [[] for i in range(n)]
for i in range(m):
	(u, v, c) = map(int, input().split())
	if not uf.same(u - 1, v - 1):
		uf.union(u - 1, v - 1)
		g[u - 1].append((v - 1, c))
		g[v - 1].append((u - 1, c))

def dfs(i):
	for (to, c) in g[i]:
		if ans[to] == -1:
			if ans[i] == c:
				if c == 1:
					ans[to] = c + 1
				else:
					ans[to] = c - 1
			else:
				ans[to] = c
			dfs(to)
ans = [-1] * n
ans[0] = 1
dfs(0)
if -1 in ans:
	print('No')
	return
ans = [a for a in ans]
print(*ans, sep='\n')


from collections import deque
(n, m) = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(m):
	(u, v, c) = list(map(int, input().split()))
	edges[u - 1].append((v - 1, c))
	edges[v - 1].append((u - 1, c))
ret = [-1] * n
q = deque([0])
ret[0] = 1
while q:
	now = q.popleft()
	for (nxt, c) in edges[now]:
		if ret[nxt] != -1:
			continue
		if ret[now] != c:
			ret[nxt] = c
		else:
			ret[nxt] = 2 if c == 1 else 1
		q.append(nxt)
print('\n'.join(map(str, ret)))


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')
MOD = 10 ** 9 + 7

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	(N, M) = LI()
	G = collections.defaultdict(list)
	for _ in range(M):
		(u, v, c) = LI_()
		G[u].append((v, c))
		G[v].append((u, c))
	ans = [-1] * N
	ans[0] = 1

	def dfs(c, p):
		for (n, l) in G[c]:
			if ans[n] == -1:
				if ans[c] == l:
					if l < N - 1:
						ans[n] = l + 1
					else:
						ans[n] = l - 1
				else:
					ans[n] = l
				dfs(n, c)
	dfs(0, -1)
	for i in ans:
		print(i + 1)

def __starting_point():
	resolve()
__starting_point()


from collections import deque

def main():
	(n, m) = map(int, input().split())
	G = dict()
	for i in range(1, n + 1):
		G[i] = dict()
	for i in range(m):
		(u, v, c) = map(int, input().split())
		G[u][v] = c
		G[v][u] = c
	done = [0] * (n + 1)
	done[1] = 1
	dq = deque()
	dq.append(1)
	while dq:
		node = dq.popleft()
		for (dst, dc) in G[node].items():
			if done[dst] == 0:
				if done[node] != dc:
					done[dst] = dc
				elif dc == n:
					done[dst] = 1
				else:
					done[dst] = dc + 1
				dq.append(dst)
	for i in range(1, n + 1):
		print(done[i])
main()


from collections import deque
(N, M) = list(map(int, input().split()))
uvc = [list(map(int, input().split())) for _ in range(M)]
G = [[] for _ in range(N + 1)]
for i in range(M):
	A = uvc[i][0]
	B = uvc[i][1]
	G[A].append([B, uvc[i][2]])
	G[B].append([A, uvc[i][2]])
seen = [0] * (N + 1)
seen[1] = G[1][0][1]
q = deque([1])
while q:
	t = q.pop()
	for (p, e) in G[t]:
		if seen[p] > 0:
			continue
		if seen[t] != e:
			seen[p] = e
		elif seen[t] + 1 <= N:
			seen[p] = seen[t] + 1
		elif seen[t] - 1 > 0:
			seen[p] = seen[t] - 1
		q.append(p)
for i in range(1, N + 1):
	if seen[i] == 0:
		print('No')
		return
for i in range(1, N + 1):
	print(seen[i])


from collections import deque
(n, m) = [int(i) for i in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v, c) = [int(i) - 1 for i in input().split()]
	g[u].append([v, c])
	g[v].append([u, c])
num = [0] * n
d = deque()
d.append(0)
label = [-1] * n
label[0] = 0
while d:
	a = d.pop()
	if num[a]:
		continue
	num[a] = 1
	for (u, c) in g[a]:
		if num[u]:
			continue
		if label[a] != c:
			label[u] = c
		elif c == 0:
			label[u] = 1
		else:
			label[u] = 0
		d.appendleft(u)
print('\n'.join(map(lambda i: str(i + 1), label)))


import sys
input = lambda : sys.stdin.readline().rstrip()
import copy
(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
g = [[] for i in range(n)]
for (x, y, z) in a:
	g[x - 1].append((y - 1, z))
	g[y - 1].append((x - 1, z))
from collections import deque

def tree(s):
	INF = -10 ** 9
	dis = [INF for i in range(n)]
	ans = [0] * n
	dis[s] = 0
	ans[s] = 1

	def bfs():
		d = deque()
		d.append(s)
		while len(d):
			x = d.popleft()
			for i in range(len(g[x])):
				y = g[x][i][0]
				if dis[y] == INF:
					d.append(y)
					dis[y] = dis[x] + 1
					if ans[y] == 0:
						if ans[x] == g[x][i][1]:
							if ans[x] == n:
								ans[y] = n - 1
							else:
								ans[y] = copy.copy(ans[x]) + 1
						else:
							ans[y] = copy.copy(g[x][i][1])
		return ans
	return bfs()
v = tree(0)
for i in v:
	print(i)


from collections import deque
(n, m) = map(int, input().split())
N = [0] * n
L = [list() for i in range(n)]
for i in range(m):
	(u, v, c) = map(int, input().split())
	L[~-u].append([~-v, c])
	L[~-v].append([~-u, c])
(N[0], Q) = (1, deque([0]))
while Q:
	u = Q.popleft()
	for (v, c) in L[u]:
		if N[v]:
			continue
		Q.append(v)
		if N[u] != c:
			N[v] = c
		else:
			N[v] = 1 if c != 1 else 2
print(*N, sep='\n')


import numpy as np

def solve(N, G):
	q = np.zeros(N, dtype=np.uint32)
	q[0] = 1
	labels = np.zeros(N + 1, dtype=np.uint32)
	labels[1] = 1
	end = 1
	for head in range(N):
		u = q[head]
		if u < 1:
			break
		for v in list(G[u].keys()):
			if labels[v] > 0:
				continue
			labels[v] = G[u][v] if labels[u] != G[u][v] else labels[u] % N + 1
			q[end] = v
			end += 1
	else:
		return labels[1:]
	return ['No']

def main():
	(N, M) = [int(x) for x in input().split()]
	G = {}
	for i in range(M):
		(u, v, c) = [int(x) for x in input().split()]
		for (u_, v_) in ((u, v), (v, u)):
			if u_ not in G:
				G[u_] = {}
			G[u_][v_] = c
	ans = solve(N, G)
	for i in range(len(ans)):
		print(ans[i])
main()


from collections import deque

def solve(start, adj):
	N = len(adj)
	ans = [0] * N
	ans[start] = 1
	que = deque([start])
	visited = set()
	while que:
		frm = que.popleft()
		visited.add(frm)
		for (to, c) in adj[frm]:
			if to in visited:
				continue
			if ans[frm] == c:
				ans[to] = c % N + 1
			else:
				ans[to] = c
			que.append(to)
	return ans

def main():
	(N, M) = list(map(int, input().split()))
	adj = {i: list() for i in range(N)}
	for i in range(M):
		(u, v, c) = list(map(int, input().split()))
		adj[u - 1].append((v - 1, c))
		adj[v - 1].append((u - 1, c))
	ans = solve(0, adj)
	for a in ans:
		print(a)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 6)
f = lambda : map(int, input().split())
(n, m) = f()
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v, l) = f()
	g[u - 1] += [(v - 1, l)]
	g[v - 1] += [(u - 1, l)]
a = [0] * n

def dfs(v, p=-1, l=1):
	a[v] = l
	for (c, m) in g[v]:
		if c == p or a[c]:
			continue
		if l == m:
			m = 1 + (m == 1)
		dfs(c, v, m)
dfs(0)
print(*a, sep='\n')


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
(N, M, *UVC) = map(int, open(0).read().split())
E = [[] for _ in range(N + 1)]
for (u, v, c) in zip(*[iter(UVC)] * 3):
	E[u].append((v, c))
	E[v].append((u, c))
memo = [-1] * (N + 1)
memo[1] = 1

def dfs(cur, par):
	for (nxt, c) in E[cur]:
		if memo[nxt] != -1 or nxt == par:
			continue
		if memo[cur] == c:
			c = 1 + (c == 1)
		memo[nxt] = c
		dfs(nxt, cur)
dfs(1, 0)
for m in memo[1:]:
	print(m)


import sys
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
	(u, v, c) = map(int, input().split())
	graph[u - 1].append((v - 1, c))
	graph[v - 1].append((u - 1, c))

def dfs(node):
	for (c_node, label) in graph[node]:
		if seen[c_node]:
			continue
		seen[c_node] = True
		if ans[node] == label:
			if label == 1:
				ans[c_node] = 2
			else:
				ans[c_node] = 1
		else:
			ans[c_node] = label
		dfs(c_node)
ans = [None] * n
ans[0] = 1
seen = [False] * n
seen[0] = True
dfs(0)
for i in ans:
	print(i)


def main():
	from collections import deque
	import sys
	input = sys.stdin.readline
	(n, m) = map(int, input().split())
	g = tuple((list() for _ in range(n)))
	for _ in range(m):
		(u, v, c) = (int(x) - 1 for x in input().split())
		g[u].append((v, c))
		g[v].append((u, c))

	def make_tree(r, g):
		ret = tuple((list() for _ in range(n)))
		dq = deque()
		dq.append(r)
		vis = [False] * n
		vis[r] = True
		while dq:
			v = dq.popleft()
			for (u, c) in g[v]:
				if vis[u]:
					continue
				vis[u] = True
				ret[v].append((u, c))
				dq.append(u)
		return ret
	gt = make_tree(0, g)

	def make_label(r, g):
		ret = [-1] * n
		ret[r] = 0
		dq = deque()
		dq.append(r)
		while dq:
			v = dq.popleft()
			for (u, c) in g[v]:
				if ret[v] == c:
					ret[u] = (c + 1) % n
				else:
					ret[u] = c
				dq.append(u)
		return ret
	label = make_label(0, gt)
	ans = map(lambda e: e + 1, label)
	print(*ans, sep='\n')

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.parents[self.find(x)]

	def kruskal(self, edge):
		edge.sort()
		cost_sum = 0
		for (cost, node1, node2) in edge:
			if not self.same(node1, node2):
				cost_sum += cost
				self.union(node1, node2)
		return cost_sum

def resolve():

	def dfs(v):
		for (d, u) in edge[v]:
			if uf.same(v, u):
				continue
			uf.union(u, v)
			if res[v] != d:
				res[u] = d
			else:
				for i in range(1, n + 1):
					if i != d:
						res[u] = i
						break
			dfs(u)
	(n, m) = map(int, input().split())
	edge = [[] for _ in range(n)]
	for _ in range(m):
		(u, v, c) = map(int, input().split())
		edge[u - 1].append([c, v - 1])
		edge[v - 1].append([c, u - 1])
	uf = UnionFind(n)
	res = [0] * n
	res[0] = 1
	dfs(0)
	print(*res, sep='\n')

def __starting_point():
	resolve()
__starting_point()


import sys
from collections import deque
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
(c, to) = (dict(), [[] for _ in range(N)])

def maxmin(x, y):
	if x < y:
		(x, y) = (y, x)
	return (x, y)
for i in range(M):
	(x, y, z) = list(map(int, input().split()))
	(x, y) = (x - 1, y - 1)
	(x, y) = maxmin(x, y)
	c[x, y] = z
	to[x].append(y)
	to[y].append(x)
d = deque()
d.append(0)
seen = [False] * N
seen[0] = True
mark = [1] * N
while len(d) > 0:
	now = d.popleft()
	for next in to[now]:
		if seen[next]:
			continue
		seen[next] = True
		d.append(next)
		xy = maxmin(next, now)
		if mark[now] == c[xy]:
			mark[next] = mark[now] % N + 1
		else:
			mark[next] = c[xy]
for i in mark:
	print(i)


from collections import Counter, deque
(n, m) = map(int, input().split())
lst = [[] for _ in range(n)]
for i in range(m):
	(u, v, c) = map(int, input().split())
	lst[u - 1].append((v - 1, c))
	lst[v - 1].append((u - 1, c))
ans = [1] + [0] * (n - 1)
q = deque([0])
while q:
	x = q.pop()
	for (i, j) in lst[x]:
		if ans[i] != 0:
			continue
		if j == ans[x]:
			if j == n:
				ans[i] = 1
			else:
				ans[i] = j + 1
		else:
			ans[i] = j
		q.append(i)
print(*ans, sep='\n')


from sys import stdin, setrecursionlimit
import bisect, collections, copy, heapq, itertools, math, string
setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 1000000007

def input():
	return stdin.readline().strip()
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = collections.defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members

	def __str__(self):
		return '\n'.join((f'{r}: {m}' for (r, m) in self.all_group_members().items()))

def main():
	(n, m) = map(int, input().split())
	uf = UnionFind(n)
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(u, v, c) = map(int, input().split())
		u -= 1
		v -= 1
		if uf.same(u, v):
			continue
		adj[u].append((v, c))
		adj[v].append((u, c))
		uf.union(u, v)
	queue = collections.deque([0])
	ans = [-1] * n
	ans[0] = 1
	while queue:
		now = queue.popleft()
		pnum = ans[now]
		for edge in adj[now]:
			child = edge[0]
			enum = edge[1]
			if ans[child] != -1:
				continue
			queue.append(child)
			if pnum == enum:
				ans[child] = 1 if pnum != 1 else 2
			else:
				ans[child] = enum
	print(*ans, sep='\n')
	return

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v, c) = list(map(int, input().split()))
	g[u - 1].append((v - 1, c))
	g[v - 1].append((u - 1, c))
s = [0]
d = [1] * n
d[0] = 0
g2 = [[] for _ in range(n)]
while s:
	p = s.pop()
	for (node, label) in g[p]:
		if d[node]:
			d[node] = 0
			s.append(node)
			g2[p].append((node, label))
			g2[node].append((p, label))
s = [0]
d = [-1] * n
d[0] = 1
while s:
	p = s.pop()
	for (node, label) in g2[p]:
		if d[node] == -1:
			if d[p] == label:
				if label == n:
					d[node] = 1
				else:
					d[node] = label + 1
			else:
				d[node] = label
			s.append(node)
for x in d:
	print(x)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
uvc = [list(map(int, input().split())) for _ in range(M)]
edge = [[] for i in range(N)]
for (u, v, c) in uvc:
	u -= 1
	v -= 1
	c -= 1
	edge[u].append((v, c))
	edge[v].append((u, c))
label = [-1] * N
label[0] = 0
Q = [0]
while Q:
	v = Q.pop()
	for (u, l) in edge[v]:
		if label[u] != -1:
			continue
		Q.append(u)
		if label[v] != l:
			label[u] = l
		else:
			label[u] = l + 1
print(*(l + 1 for l in label), sep='\n')


from collections import deque

def solve(N, M, uvc):
	tree_map = [[] for _ in range(N + 1)]
	for (u, v, c) in uvc:
		tree_map[u].append([v, c])
		tree_map[v].append([u, c])
	ans = [0] * (N + 1)
	visited = [False] * (N + 1)
	visited[1] = True
	ans[1] = 1
	dq = deque([1])
	while dq:
		now = dq.popleft()
		for (child, c) in tree_map[now]:
			if visited[child]:
				continue
			visited[child] = True
			if c == ans[now]:
				ans[child] = c % N + 1
			else:
				ans[child] = c
			dq.append(child)
	[print(i) for i in ans[1:]]

def __starting_point():
	(N, M) = map(int, input().split())
	uvc = [[int(i) for i in input().split()] for _ in range(M)]
	solve(N, M, uvc)
__starting_point()


import sys
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
uvc = [list(map(int, input().split())) for _ in range(M)]
g = [[] for _ in range(N)]
for (u, v, c) in uvc:
	u -= 1
	v -= 1
	g[u].append((v, c))
	g[v].append((u, c))
children = [[] for _ in range(N)]
appeared = [False] * N
q = [0]
appeared[0] = True
while q:
	u = q.pop()
	for (v, c) in g[u]:
		if not appeared[v]:
			children[u].append((v, c))
			q.append(v)
			appeared[v] = True
colors = [None] * N
colors[0] = 1
q = [0]
while q:
	u = q.pop()
	c_u = colors[u]
	for (v, c_edge) in children[u]:
		colors[v] = c_edge + (c_edge == c_u)
		q.append(v)
print('\n'.join(map(str, colors)))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inps():
	return input().rstrip()

def inpl():
	return list(map(int, input().split()))

def inpls():
	return list(map(str, input().split()))

def _debug(obj):
	print(obj, file=sys.stderr)
from math import gcd, floor, ceil, factorial
import itertools as it
from collections import deque, defaultdict
from collections import Counter

def lcd(a, b):
	return a * b // gcd(a, b)

def chmin(dp, i, x):
	if x < dp[i]:
		dp[i] = x
		return True
	return False

def chmax(dp, i, x):
	if x > dp[i]:
		dp[i] = x
		return True
	return False
(N, M) = inpl()
graph = [[] for i in range(N)]
for i in range(M):
	(u, v, c) = inpl()
	graph[u - 1].append([v - 1, c])
	graph[v - 1].append([u - 1, c])
ans = [0] * N
ans[0] = 1
q = deque()
q.append(0)
while True:
	if not q:
		break
	i = q.popleft()
	for g in graph[i]:
		j = g[0]
		c = g[1]
		if ans[j] != 0:
			continue
		if ans[i] == c:
			if c + 1 <= N:
				ans[j] = c + 1
			else:
				ans[j] = c - 1
		else:
			ans[j] = c
		q.append(j)
for i in ans:
	print(i)


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(map(int, input().split()))
mod = 10 ** 9 + 7
from collections import defaultdict

class UnionFind:

	def __init__(self, N: int):
		self.N = N
		self.root = [-1] * N
		self.rank = [0] * N

	def __repr__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

	def find(self, x: int):
		if self.root[x] < 0:
			return x
		else:
			while self.root[x] >= 0:
				x = self.root[x]
			return x

	def union(self, x: int, y: int):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def same(self, x: int, y: int):
		return self.find(x) == self.find(y)

	def count(self, x):
		return -self.root[self.find(x)]

	def members(self, x):
		_root = self.find(x)
		return [i for i in range(self.N) if self.find == _root]

	def roots(self):
		return [i for (i, x) in enumerate(self.root) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		dd = defaultdict(list)
		for i in range(N):
			root = self.find(i)
			dd[root].append(i)
		return dd

def Kruskal(maxV, edges):
	edges.sort()
	newAdj = [[] for _ in range(N)]
	uf = UnionFind(maxV)
	ans = 0
	for e in edges:
		fro = e[0]
		to = e[1]
		if uf.find(fro) != uf.find(to):
			uf.union(fro, to)
			ans += e[0]
			newAdj[fro].append(to)
			newAdj[to].append(fro)
	return newAdj
(N, M) = MI()
from collections import defaultdict
dd = defaultdict(int)
Edge = []
for _ in range(M):
	(u, v, c) = MI()
	u -= 1
	v -= 1
	c -= 1
	if dd[u, v]:
		continue
	Edge.append((u, v))
	dd[u, v] = c
	dd[v, u] = c
adj = Kruskal(N, Edge)
Col = [-1] * N
import queue
q = queue.Queue()
for v in adj[0]:
	q.put((v, 0))
while not q.empty():
	(v, p) = q.get()
	if Col[p] != dd[v, p]:
		Col[v] = dd[v, p]
	elif Col[p] == 0:
		Col[v] = 1
	else:
		Col[v] = 0
	for nv in adj[v]:
		if nv == 0 or Col[nv] != -1:
			continue
		q.put((nv, v))
col_0 = [0] * N
for v in adj[0]:
	col_0[Col[v]] += 1
for i in range(N):
	if col_0[i] == 0:
		Col[0] = i
		break
for i in range(N):
	print(Col[i] + 1)


from collections import deque

class Unionfind:

	def __init__(self, n):
		self.uf = [-1] * n

	def find(self, x):
		if self.uf[x] < 0:
			return x
		else:
			self.uf[x] = self.find(self.uf[x])
			return self.uf[x]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return False
		if self.uf[x] > self.uf[y]:
			(x, y) = (y, x)
		self.uf[x] += self.uf[y]
		self.uf[y] = x
		return True

	def size(self, x):
		x = self.find(x)
		return -self.uf[x]
(n, m) = map(int, input().split())
e = [[] for i in range(n + 1)]
uf = Unionfind(n + 1)
for i in range(m):
	(u, v, c) = map(int, input().split())
	if uf.same(u, v):
		continue
	e[u].append((v, c))
	e[v].append((u, c))
ans = [-1] * (n + 1)
ans[1] = 1
q = deque([[1, 0]])
while q:
	(now, par) = q.popleft()
	for (nex, col) in e[now]:
		if ans[nex] > 0:
			continue
		if ans[now] == col:
			ans[nex] = col % n + 1
		else:
			ans[nex] = col
		q.append([nex, now])
for i in ans[1:]:
	print(i)


from collections import deque
(N, M) = list(map(int, input().split()))
G = [{} for i in range(N)]
for _ in range(M):
	(u, v, c) = list(map(int, input().split()))
	G[u - 1][v - 1] = c - 1
	G[v - 1][u - 1] = c - 1
ans = [-1 for i in range(N)]
ans[0] = 0
q = deque([0])
while q:
	r = q.pop()
	for p in G[r]:
		if ans[p] != -1:
			continue
		if ans[r] == G[p][r]:
			ans[p] = (ans[r] + 1) % N
		else:
			ans[p] = G[p][r]
		q.append(p)
for i in ans:
	print(i + 1)


(N, M) = map(int, input().split())
P = [-1] * (N + 1)
Visited = [False] * (N + 1)
Past = [[] for i in range(N + 1)]
for i in range(M):
	(u, v, c) = map(int, input().split())
	Past[u].append((v, c))
	Past[v].append((u, c))
from queue import Queue
q = Queue()
q.put(1)
P[1] = 1
while not q.empty():
	st = q.get()
	for (to, c) in Past[st]:
		if P[to] == -1:
			if P[st] == c:
				P[to] = c + 1 if c + 1 <= N else 1
			else:
				P[to] = c
			q.put(to)
flag = True
for i in range(1, N + 1):
	if P[i] == -1:
		flag = False
if flag:
	for i in range(1, N + 1):
		print(P[i])
else:
	print('No')


import sys
input = sys.stdin.readline
from collections import defaultdict, deque
mod = 10 ** 9 + 7
INF = float('inf')

def getlist():
	return list(map(int, input().split()))

class UnionFind(object):

	def __init__(self, N):
		self.par = [i for i in range(N)]
		self.rank = [0] * N

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

class Graph(object):

	def __init__(self, N):
		self.graph = [[] for i in range(N)]

	def add_edge(self, a, b, c):
		self.graph[a].append((b, c))

def bfs(G, s, N):
	Q = deque()
	Q.append(s)
	visit = [0] * N
	visit[s] = 1
	label = [None] * N
	label[s] = 0
	while Q:
		v = Q.popleft()
		for (i, c) in G.graph[v]:
			if visit[i] == 0:
				visit[i] = 1
				if c != label[v]:
					label[i] = c
				elif c == N - 1:
					label[i] = 0
				else:
					label[i] = N - 1
				Q.append(i)
	return label

def main():
	(N, M) = getlist()
	G = Graph(N)
	UF = UnionFind(N)
	for i in range(M):
		(u, v, c) = getlist()
		u -= 1
		v -= 1
		c -= 1
		if UF.same_check(u, v) == False:
			UF.union(u, v)
			G.add_edge(u, v, c)
			G.add_edge(v, u, c)
	ans = bfs(G, 0, N)
	for i in ans:
		print(i + 1)

def __starting_point():
	main()
__starting_point()


import sys
from collections import deque
(N, M) = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
	(u, v, c) = map(int, sys.stdin.readline().split())
	u -= 1
	v -= 1
	edge[u].append((v, c))
	edge[v].append((u, c))
path = [-1] * N
path[0] = edge[0][0][1]
q = deque()
for (v, c) in edge[0]:
	q.append((0, v, c))
while q:
	(u, v, c) = q.popleft()
	if path[v] == -1:
		if path[u] != c:
			vc = c
		elif path[u] > 1:
			vc = path[u] - 1
		else:
			vc = path[u] + 1
		path[v] = vc
		for (nv, nc) in edge[v]:
			if path[nv] == -1:
				q.append((v, nv, nc))
print(*path, sep='\n')


import sys
input = sys.stdin.readline
from itertools import groupby
from collections import deque
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())

def HalfDead():
	(n, m) = R()
	g = dict()
	for i in range(1, n + 1):
		g[i] = dict()
	for i in range(m):
		(u, v, c) = R()
		g[u][v] = c
		g[v][u] = c
	color = [0] * (n + 2)
	color[1] = 1
	dq = deque()
	dq.append(1)
	while dq:
		frm = dq.popleft()
		for (to, c) in g[frm].items():
			if color[to] == 0:
				if color[frm] != c:
					color[to] = c
				elif c == n:
					color[to] = 1
				else:
					color[to] = c + 1
				dq.append(to)
	for i in range(n):
		print(color[i + 1])
	return

def __starting_point():
	HalfDead()
__starting_point()


from collections import deque

def bfs():
	q = deque()
	q.append(1)
	ans[1] = 1
	while q:
		i = q.popleft()
		for (j, c) in G[i]:
			if ans[j] == 0:
				if not ans[i] == c:
					ans[j] = c
				else:
					ans[j] = 1 if ans[i] >= 2 else 2
				q.append(j)
	return
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v, c) = map(int, input().split())
	G[u].append([v, c])
	G[v].append([u, c])
ans = [0] * (n + 1)
bfs()
for i in range(1, n + 1):
	print(ans[i])


from collections import deque
(N, M) = list(map(int, input().split()))
G = [[] for _ in range(N)]
for i in range(M):
	(u, v, c) = list(map(int, input().split()))
	G[u - 1].append((v - 1, c))
	G[v - 1].append((u - 1, c))
newG = [[] for _ in range(N)]
done = [0] * N
ans = [0] * N
que = deque([0])
ans[0] = 1
while que:
	start = que.popleft()
	done[start] = 1
	for t in G[start]:
		(nex, c) = t
		if done[nex] == 1:
			continue
		else:
			newG[start].append((nex, c))
			que.append(nex)
			if ans[start] == c:
				ans[nex] = c % N + 1
			else:
				ans[nex] = c
for a in ans:
	print(a)


import sys
input = sys.stdin.readline
from collections import Counter, deque
(n, m) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(m)]
F = []
(*p,) = range(n)

def root(x):
	if x == p[x]:
		return x
	p[x] = y = root(p[x])
	return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if px == py:
		return 0
	if px < py:
		p[py] = px
	else:
		p[px] = py
	return 1
E.sort()
ans = 0
for (v, w, c) in E:
	if unite(v - 1, w - 1):
		F.append([v, w, c])
		ans += c
g = [[] for i in range(n)]
ans = [0] * n
ans[0] = '?'
used = [False] * (n + 1)
pre = [0] * n
for (u, v, c) in F:
	g[u - 1].append([v - 1, c])
	g[v - 1].append([u - 1, c])
Q = deque()
Q.append(0)
while Q:
	p = Q.popleft()
	for s in g[p]:
		(i, v) = (s[0], s[1])
		if ans[i] == 0:
			if ans[p] == v:
				ans[i] = v + 1
				Q.append(i)
				if ans[i] == n + 1:
					ans[i] = 1
			else:
				ans[i] = v
				Q.append(i)
for (i, v) in g[0]:
	used[v] = True
for i in range(1, n + 1):
	if used[i] == False:
		ans[0] = i
		break
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(now):
	for (nxt, color) in edge[now]:
		if res[nxt] == 0:
			if res[now] == color:
				res[nxt] = color + 1 if color < n else 1
			else:
				res[nxt] = color
			dfs(nxt)
	return
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
	(u, v, c) = map(int, input().split())
	edge[u - 1].append([v - 1, c])
	edge[v - 1].append([u - 1, c])
res = [0] * n
res[0] = 1
dfs(0)
print(*res, sep='\n')


from collections import defaultdict
from collections import deque

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members

	def __str__(self):
		return '\n'.join((f'{r}: {m}' for (r, m) in list(self.all_group_members().items())))
(n, m) = list(map(int, input().split()))
V = [[] for i in range(n + 1)]
sets = [set([]) for i in range(n + 1)]
uf = UnionFind(n + 1)
for i in range(m):
	(a, b, c) = list(map(int, input().split()))
	if uf.find(a) != uf.find(b):
		uf.union(a, b)
		V[a].append([b, c])
		V[b].append([a, c])
		sets[a].add(c)
		sets[b].add(c)
p = [-1] * (n + 1)

def out_not_in_number(x):
	ret = -1
	for i in range(1, n + 1):
		if i not in sets[x]:
			ret = i
			break
	return ret
start = 1
p[start] = out_not_in_number(start)
q = deque([])
q.append(start)
while q:
	x = q.popleft()
	for (y, z) in V[x]:
		if p[y] == -1:
			q.append(y)
			if p[x] == z:
				p[y] = out_not_in_number(y)
			else:
				p[y] = z
for i in range(1, n + 1):
	print(p[i])


from collections import deque
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(m):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	edge[u].append((v, c))
	edge[v].append((u, c))
que = deque([0])
used = [0] * (n + 1)
used[0] = 1
while que:
	v = que.pop()
	for (u, cost) in edge[v]:
		if used[u]:
			continue
		if used[v] == cost:
			used[u] = cost % n + 1
		else:
			used[u] = cost
		que.appendleft(u)
for i in range(n):
	print(used[i])


from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members

	def __str__(self):
		return '\n'.join((f'{r}: {m}' for (r, m) in list(self.all_group_members().items())))
(n, m) = list(map(int, input().split()))
un = UnionFind(n)
next_edge_dic = {}
flag = False
for _ in range(m):
	(u, v, c) = list(map(int, input().split()))
	u -= 1
	v -= 1
	if not un.same(u, v):
		if u not in next_edge_dic:
			next_edge_dic[u] = []
		next_edge_dic[u].append([v, c])
		if v not in next_edge_dic:
			next_edge_dic[v] = []
		next_edge_dic[v].append([u, c])
		un.union(u, v)
	if un.size(0) == n:
		flag = True
		break
if not flag:
	print('No')
else:
	stack = [0]
	visited = set([0])
	ans = [0] * n
	ans[0] = 1
	while stack:
		edge = stack.pop()
		for (next_edge, label) in next_edge_dic[edge]:
			if next_edge in visited:
				continue
			if ans[edge] == label:
				if label == 1:
					ans[next_edge] = 2
				else:
					ans[next_edge] = 1
			else:
				ans[next_edge] = label
			stack.append(next_edge)
		visited.add(edge)
	for i in range(n):
		print(ans[i])


def main():
	(n, m) = map(int, input().split())
	G = [-1] * n
	Node = {}
	for i in range(n):
		Node[i + 1] = []
	for i in range(m):
		(u, v, c) = map(int, input().split())
		Node[u] += [[v, c]]
		Node[v] += [[u, c]]
	que = [0]
	G[0] = 1
	while len(que) > 0:
		q = que.pop(0)
		for (nv, w) in Node[q + 1]:
			if G[nv - 1] != -1:
				continue
			if G[q] == w:
				G[nv - 1] = (G[q] + 1) % n
			else:
				G[nv - 1] = w
			que.append(nv - 1)
	cnt = 0
	for i in range(n):
		if G[i] == -1:
			cnt += 1
	if cnt > 0:
		print('No')
		return
	for i in range(n):
		print(G[i])

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v, c) = map(int, input().split())
	G[u].append((v, c))
	G[v].append((u, c))
q = 1
stack = [1]
ans = [0] * (n + 1)
ans[1] = 1
while stack:
	v = stack.pop()
	for (u, c) in G[v]:
		if not ans[u]:
			if ans[v] == c:
				c = c % n + 1
			ans[u] = c
			stack.append(u)
			q += 1
			if q == n:
				stack = []
				break
if q == n:
	print(*ans[1:], sep='\n')
else:
	print('No')


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	edges[u].append((v, c))
	edges[v].append((u, c))
ans = [-1] * N
ans[0] = 1

def dfs(u):
	for (v, c) in edges[u]:
		if ans[v] != -1:
			continue
		if ans[u] == c:
			if c == 1:
				ans[v] = 2
			else:
				ans[v] = 1
		else:
			ans[v] = c
		dfs(v)
dfs(0)
print(*ans, sep='\n')


import sys
input = lambda : sys.stdin.readline()
(n, m) = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y, c) = list(map(int, input().split()))
	g[x].append((y, c))
	g[y].append((x, c))
que = [1]
num = [0] * (n + 1)
num[1] = 1
while que:
	x = que.pop()
	for (v, nv) in g[x]:
		if num[v]:
			continue
		if num[x] == nv:
			num[v] = nv % n + 1
		else:
			num[v] = nv
		que.append(v)
print('\n'.join(map(str, num[1:])))


from collections import defaultdict, deque
(n, m) = map(int, input().split())
G = defaultdict(list)
for _ in range(m):
	(i, j, w) = map(int, input().split())
	G[i].append((j, w))
	G[j].append((i, w))
ans = [0] * (n + 1)
ans[1] = 1
q = deque([1])
while q:
	node = q.popleft()
	for (nei, w) in G[node]:
		if ans[nei]:
			continue
		if ans[node] == w:
			ans[nei] = w + 1 if w < n else 1
		else:
			ans[nei] = w
		q.append(nei)
for i in range(n):
	print(ans[i + 1])


from collections import deque
(N, M) = list(map(int, input().split()))
(c, to) = (dict(), [[] for _ in range(N)])

def maxmin(x, y):
	if x < y:
		(x, y) = (y, x)
	return (x, y)
for i in range(M):
	(x, y, z) = list(map(int, input().split()))
	(x, y) = (x - 1, y - 1)
	(x, y) = maxmin(x, y)
	if (x, y) not in c:
		c[x, y] = z
		to[x].append(y)
		to[y].append(x)
q = deque([0])
mark = [0] * N
mark[0] = 1
while q:
	now = q.popleft()
	for next in to[now]:
		if mark[next]:
			continue
		cost = c[maxmin(now, next)]
		if mark[now] == cost:
			mark[next] = mark[now] % N + 1
		else:
			mark[next] = cost
		q.append(next)
for i in mark:
	print(i)


(N, M) = list(map(int, input().split()))
edges = [list([int(x) - 1 for x in input().split()]) for _ in range(M)]
adges = [[] for _ in range(N)]
for (u, v, c) in edges:
	adges[u].append([v, c])
	adges[v].append([u, c])
visited = [False] * N
cur = edges[0][0]
visited[cur] = True
Q = [cur]
use_edges = []
while Q:
	cur = Q.pop()
	for (nex, label) in adges[cur]:
		if visited[nex]:
			continue
		else:
			Q.append(nex)
			visited[nex] = True
			use_edges.append([cur, nex, label])
if all((v for v in visited)):
	pass
else:
	print('No')
	return
ans = [-1] * N
adj_use = [[] for _ in range(N)]
for (u, v, c) in use_edges:
	adj_use[u].append([v, c])
	adj_use[v].append([u, c])
cur = None
for i in range(N):
	if len(adj_use[i]) == 1:
		cur = i
		break
for (u, v, l) in use_edges:
	if u == cur or v == cur:
		if l == 0:
			ans[cur] = 1
		else:
			ans[cur] = 0
		break
Q = [cur]
while Q:
	cur = Q.pop()
	for (nex, label) in adj_use[cur]:
		if ans[nex] != -1:
			continue
		else:
			Q.append(nex)
			if ans[cur] == label:
				ans[nex] = (label + 1) % N
			else:
				ans[nex] = label
for a in ans:
	print(a + 1)


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			(x, y) = (y, x)
		if self.rank[x] == self.rank[y]:
			self.rank[x] += 1
		self.par[y] = x
(N, M) = MI()
Graph = [[] for _ in range(N + 1)]
UF = UnionFind(N)
for _ in range(M):
	(u, v, c) = MI()
	if not UF.same_check(u, v):
		UF.unite(u, v)
		Graph[u].append((v, c))
		Graph[v].append((u, c))
deq = deque([1])
ANS = [-1] * (N + 1)
ANS[1] = 1
while deq:
	i = deq.pop()
	for (j, c) in Graph[i]:
		if ANS[j] != -1:
			continue
		if ANS[i] != c:
			ANS[j] = c
		elif c == 1:
			ANS[j] = 2
		else:
			ANS[j] = 1
		deq.append(j)
print(*ANS[1:], sep='\n')


from collections import deque
(N, M) = list(map(int, input().split()))
Edge = [[] for _ in range(N)]
for _ in range(M):
	(u, v, c) = list(map(int, input().split()))
	u -= 1
	v -= 1
	Edge[u].append((v, c))
	Edge[v].append((u, c))
Ans = [-1] * N
Ans[0] = 1
Q = deque()
Q.append(0)
while Q:
	now = Q.popleft()
	for (nex, color) in Edge[now]:
		if Ans[nex] != -1:
			continue
		if color == Ans[now]:
			Ans[nex] = color + 1
			Q.append(nex)
		else:
			Ans[nex] = color
			Q.append(nex)
if -1 in Ans:
	print('No')
else:
	for ans in Ans:
		print(ans)


import sys
sys.setrecursionlimit(10 ** 8)

class union_find:

	def __init__(self, n):
		self.par = [-1] * n

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x != y:
			if x > y:
				(x, y) = (y, x)
			self.par[x] += self.par[y]
			self.par[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.par[self.find(x)]
(n, m) = map(int, input().split())
gragh = [[] for _ in range(n)]
ans = [-1] * n

def dfs(now):
	for (nex, c) in gragh[now]:
		if ans[nex] != -1:
			continue
		if ans[now] == c:
			ans[nex] = (c + 1) % n + 1
		else:
			ans[nex] = c
		dfs(nex)

def main():
	tree = union_find(n)
	for i in range(m):
		(u, v, c) = map(int, input().split())
		if not tree.same(u - 1, v - 1):
			tree.unite(u - 1, v - 1)
			gragh[u - 1].append([v - 1, c])
			gragh[v - 1].append([u - 1, c])
	ans[0] = 1
	dfs(0)
	for i in ans:
		print(i)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
UVC = [[int(x) for x in input().split()] for _ in range(M)]
tree = [[] for _ in range(N)]
for (u, v, c) in UVC:
	u -= 1
	v -= 1
	tree[u].append((v, c))
	tree[v].append((u, c))
result = [0] * N
result[0] = 1
stack = [0]
while stack:
	current = stack.pop()
	for (child, label) in tree[current]:
		if result[child] != 0:
			continue
		stack.append(child)
		if result[current] == label:
			result[child] = label + 1 if label < N else 1
		else:
			result[child] = label
print(*result, sep='\n')


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
uf = UnionFind(n)
for _ in range(m):
	(u, v, c) = map(lambda x: int(x) - 1, input().split())
	if uf.find(u) != uf.find(v):
		g[u].append([v, c])
		g[v].append([u, c])
		uf.union(u, v)
node_val = [None] * n
node_val[0] = 0
que = [0]
seen = set()
while que != []:
	temp = []
	for node in que:
		if node in seen:
			continue
		for (next_node, c) in g[node]:
			if next_node in seen:
				continue
			if node_val[node] == c:
				node_val[next_node] = (c + 1) % n
			else:
				node_val[next_node] = c
			temp.append(next_node)
		seen.add(node)
	que = temp
for val in node_val:
	print(val + 1)


from sys import stdin
import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = list(map(int, stdin.readline().split()))
g = [[] for i in range(0, N)]
for i in range(0, M):
	(a, b, c) = list(map(int, stdin.readline().split()))
	a -= 1
	b -= 1
	g[a].append((b, c))
	g[b].append((a, c))
vis = [False] * N
col = [-1] * N

def dfs(v):
	nonlocal vis
	nonlocal col
	vis[v] = True
	for (to, c) in g[v]:
		if vis[to] == True:
			continue
		if c == col[v]:
			if c == 1:
				col[to] = 2
			else:
				col[to] = 1
		else:
			col[to] = c
		dfs(to)
col[0] = 1
dfs(0)
for i in range(0, N):
	print(col[i])


import collections as co
(n, m) = list(map(int, input().split()))
ansDic = dict()
edgeLis = [[] for i in range(n + 1)]
for i in range(1, n + 1):
	ansDic[i] = 0
for i in range(1, m + 1):
	edge = list(map(int, input().split()))
	edgeLis[edge[0]].append([edge[1], edge[2]])
	edgeLis[edge[1]].append([edge[0], edge[2]])
q = co.deque()
q.append(1)
while len(q) > 0:
	k = q.popleft()
	if ansDic[k] == 0:
		ansDic[k] = k
	for lis in edgeLis[k]:
		l1 = lis[0]
		l2 = lis[1]
		if ansDic[l1] == 0:
			q.append(l1)
			if ansDic[k] != l2:
				ansDic[l1] = l2
			elif l1 != l2:
				ansDic[l1] = l1
			else:
				ansDic[l1] = k
for i in range(1, n + 1):
	print(ansDic[i])


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n

	def _root(self, x):
		stack = []
		tbl = self.table
		while tbl[x] >= 0:
			stack.append(x)
			x = tbl[x]
		for y in stack:
			tbl[y] = x
		return x

	def find(self, x, y):
		return self._root(x) == self._root(y)

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			if d1 == d2:
				self.table[r1] -= 1
		else:
			self.table[r1] = r2

def main():
	(N, M) = map(int, readline().split())
	all_edges = [tuple(map(int, readline().split())) for _ in range(M)]
	G = [[] for _ in range(N + 1)]
	edges = []
	edge_to_label = {}
	U = UnionFind(N + 1)
	while all_edges:
		(u, v, c) = all_edges.pop()
		if U.find(u, v):
			continue
		U.union(u, v)
		G[u].append(v)
		G[v].append(u)
		edges.append((u, v))
		edge_to_label[u, v] = c
		edge_to_label[v, u] = c
	label = [0] * (N + 1)
	label[1] = 1
	stack = [1]
	while stack:
		x = stack.pop()
		for y in G[x]:
			if label[y] > 0:
				continue
			l = edge_to_label[x, y]
			if label[x] == l:
				label[y] = (l + 1) % N + 1
				stack.append(y)
			else:
				label[y] = l
				stack.append(y)
	print(*label[1:], sep='\n')

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
UVC = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for (u, v, c) in UVC:
	(u, v) = (u - 1, v - 1)
	es[u].append((v, c))
	es[v].append((u, c))
ans = [-1] * N
ans[0] = 1
stack = [0]
visited = [0] * N
visited[0] = 1
while stack:
	v = stack.pop()
	for (to, c) in es[v]:
		if visited[to]:
			continue
		visited[to] = 1
		if ans[v] == c:
			ans[to] = c + 1 if c + 1 <= N else 1
		else:
			ans[to] = c
		stack.append(to)
print(*ans, sep='\n')


import collections
(N, M, *UVC) = [int(_) for _ in open(0).read().split()]
(U, V, C) = [UVC[_::len('UVC')] for _ in range(len('UVC'))]
CUV = []
for (u, v, c) in zip(U, V, C):
	CUV += [(c, u, v)]
CUV.sort()

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.root[self.find(x)]
uf = UnionFind(N)
G = [{} for _ in range(N + 1)]
se = set()
for (c, u, v) in CUV:
	if uf.is_same(u, v):
		continue
	uf.unite(u, v)
	se.add(c)
	G[u][v] = G[v][u] = c
other = (set(range(1, N + 1)) - se).pop()
ans = [-1] * (N + 1)
ans[1] = 1
uf2 = UnionFind(N)
S = [1]
while S:
	u = S.pop()
	for v in G[u]:
		if uf2.is_same(u, v):
			continue
		uf2.unite(u, v)
		c = G[u][v]
		ans[v] = c if c != ans[u] else c % N + 1
		S += [v]
print(*ans[1:], sep='\n')


import sys
input = sys.stdin.readline

def main():
	(N, M) = map(int, input().split())
	number = [0] * N
	edges = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, c) = map(int, input().split())
		u -= 1
		v -= 1
		edges[u].append((v, c))
		edges[v].append((u, c))
	from collections import deque
	fr = 0
	que = deque([fr])
	number[fr] = 1
	for _ in range(N ** 2):
		fr = que.popleft()
		for (to, c) in edges[fr]:
			if number[to] == 0:
				que.append(to)
				if number[fr] != c:
					number[to] = c
				elif c == 1:
					number[to] = 2
				else:
					number[to] = 1
		if len(que) == 0:
			break
	print(*number, sep='\n')

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	E[u].append((c, v))
	E[v].append((c, u))
from heapq import heappush, heappop, heapify
used = [0] * N
que = [(c, next, 0) for (c, next) in E[0]]
used[0] = 1
heapify(que)
ans = [-1] * N
ans[0] = 1
while que:
	(cv, v, pre) = heappop(que)
	if used[v]:
		continue
	used[v] = 1
	if cv == ans[pre]:
		ans[v] = N - -(cv + 1) % N
	else:
		ans[v] = cv
	for (cost, next) in E[v]:
		if used[next]:
			continue
		heappush(que, (cost, next, v))
print('\n'.join([str(i) for i in ans]))


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		self.group = {r: [] for r in self.roots()}
		for i in range(self.n):
			self.group[self.find(i)].append(i)
		return self.group

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
from collections import deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
uf = UnionFind(n)
e = [[] for _ in range(n)]
for i in range(m):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	if uf.same(u, v):
		continue
	e[u].append((v, c))
	e[v].append((u, c))
que = deque()
que.append(0)
ans = [-1] * n
ans[0] = 1
while que:
	now = que.popleft()
	for (i, j) in e[now]:
		if ans[i] != -1:
			continue
		if ans[now] == j:
			ans[i] = (j + 1) % n
			if ans[i] == 0:
				ans[i] = n
		else:
			ans[i] = j
		que.append(i)
print(*ans, sep='\n')


import sys
from collections import deque
from heapq import heappush, heappop

def input():
	return sys.stdin.readline().strip()

def main():
	(N, M) = list(map(int, input().split()))
	repn = [[] for _ in range(N + 1)]
	for _ in range(M):
		(u, v, c) = list(map(int, input().split()))
		repn[u].append((c, v))
		repn[v].append((c, u))
	visited = [0] * (N + 1)
	used_edge = [[] for _ in range(N + 1)]
	edge_q = []
	for (c, v) in repn[1]:
		heappush(edge_q, (c, 1, v))
	visited[1] = 1
	while edge_q:
		(c, u, v) = heappop(edge_q)
		if visited[v]:
			continue
		visited[v] = 1
		used_edge[u].append((c, v))
		for (nc, nv) in repn[v]:
			if not visited[nv]:
				heappush(edge_q, (nc, v, nv))
	label = [0] * (N + 1)
	cand = set(range(1, N + 1))
	for (c, v) in used_edge[1]:
		cand.discard(c)
	label[1] = cand.pop()
	q = deque()
	for (c, v) in used_edge[1]:
		q.append((c, 1, v))
	while q:
		(c, u, v) = q.popleft()
		if label[u] == c:
			label[v] = 1 if c != 1 else 2
		else:
			label[v] = c
		for (nc, nv) in used_edge[v]:
			q.append((nc, v, nv))
	for (i, l) in enumerate(label):
		if i == 0:
			continue
		print(l)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 9)
read = lambda : sys.stdin.readline()

def read_ints():
	return list(map(int, read().split()))

def read_intgrid(h):
	return list((list(map(int, read().split())) for i in range(h)))

def read_strgrid(h):
	return list((list(read()) for i in range(h)))

def main():
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	for i in range(m):
		(a, b, c) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		G[a].append((b, c))
		G[b].append((a, c))
	vis = [0] * n
	label = [-1] * n
	label[0] = 1

	def dfs(v):
		vis[v] = 1
		for (x, c) in G[v]:
			if vis[x]:
				continue
			if label[x] == -1:
				if label[v] == c:
					if label[v] == 1:
						label[x] = label[v] + 1
					else:
						label[x] = label[v] - 1
				else:
					label[x] = c
			dfs(x)
	dfs(0)
	print('\n'.join(map(str, label)))
	return None

def __starting_point():
	main()
__starting_point()