John lives in HackerLand, a country with $N$ cities and $\mbox{M}$ bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (i.e., $2$ raised to some exponent). It's possible for John to reach any city from any other city.

Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation. 

Input Format

The first line contains two space-seperated integers denoting $N$ (the number of cities) and $\mbox{M}$ (the number of roads), respectively. 

Each line $\boldsymbol{i}$ of the $\mbox{M}$ subsequent lines contains the respective values of $A_i$, $B_i$, and $C_i$ as three space-separated integers. These values define a bidirectional road between cities $A_i$ and $B_i$ having length $2^{C_i}$.

Constraints

$1\leq N\leq10^5$
$1\leq M\leq2\times10^5$
$1\leq A_i,B_i\leq N$, $A_i\neq B_i$
$0\leq C_i<M$
If $i\neq j$, then $C_i\neq C_j$.

Output Format

Find the sum of minimum distances of each pair of cities and print the answer in binary representation. 

Sample Input
5 6
1 3 5
4 5 0
2 1 3
3 2 1
4 3 4
4 2 2

Sample Output
1000100

Explanation

In the sample, the country looks like this:

Let $d(x,y)$ be the minimum distance between city $\boldsymbol{x}$ and city $y$. 

$d(1,2)=8$

$d(1,3)=10$

$d(1,4)=12$

$d(1,5)=13$

$d(2,3)=2$

$d(2,4)=4$

$d(2,5)=5$

$d(3,4)=6$

$d(3,5)=7$

$d(4,5)=1$

$Sum=8+10+12+13+2+4+5+6+7+1=(68)_{10}=(1000100)_{2}$

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
p = list(range(10 ** 5))

def dsu_get(v):
	if p[v] != v:
		p[v] = dsu_get(p[v])
	return p[v]

def dsu_merge(u, v):
	u = dsu_get(u)
	v = dsu_get(v)
	p[u] = v
	return u != v
(n, m) = map(int, input().split())
e = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	e += [(c, b - 1, a - 1)]
e.sort()
G = [[] for x in range(n)]
for (c, a, b) in e:
	if dsu_merge(a, b):
		G[a] += [(b, c)]
		G[b] += [(a, c)]
f = [0] * m

def dfs(v, par=-1):
	sz = 1
	for (u, c) in G[v]:
		if u == par:
			continue
		y = dfs(u, v)
		f[c] = y * (n - y)
		sz += y
	return sz
dfs(0)
ans = 0
for x in f[::-1]:
	ans *= 2
	ans += x
print(bin(ans)[2:])


(n, m) = map(int, input().split())
(e, E) = ([], [[] for _ in range(n + 1)])
(p, h, k) = ([i for i in range(n + 1)], [1] * (n + 1), [1] * (n + 1))
for i in range(m):
	(i, j, c) = map(int, input().split())
	e += [(c, i, j)]
e.sort()

def per(nom):
	if p[nom] != nom:
		p[nom] = per(p[nom])
	return p[nom]

def uni(cc, aa, bb):
	(a, b) = (per(aa), per(bb))
	if a == b:
		return
	if h[a] == h[b]:
		h[a] += 1
	if h[a] < h[b]:
		(a, b) = (b, a)
	p[b] = a
	E[aa] += [(bb, cc)]
	E[bb] += [(aa, cc)]
for (cc, aa, bb) in e:
	uni(cc, aa, bb)
(st, ans) = ([], 0)
for i in range(1, n + 1):
	if len(E[i]) == 1:
		ch = [(0, i, 0)]
		break
while ch:
	(a, b, c) = ch.pop()
	st += [(a, b, c)]
	for (x, y) in E[b]:
		if x == a:
			continue
		ch += [(b, x, y)]
while st:
	(a, b, c) = st.pop()
	ans += (1 << c) * k[b] * (n - k[b])
	k[a] += k[b]
print(bin(ans)[2:])


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

def foo(x):
	return (x[0] - 1, x[1] - 1, x[2])
(N, M) = read_line()
edges = sorted([foo(read_line()) for _ in range(M)], key=lambda x: x[2])
parents = [i for i in range(N)]
sizes = [1] * N

def root(x):
	y = x
	while y != parents[y]:
		y = parents[y]
	while x != parents[x]:
		parents[x] = y
		x = parents[x]
	return x

def union(x, y):
	x2 = root(x)
	y2 = root(y)
	if sizes[x2] < sizes[y2]:
		parents[x2] = y2
	else:
		parents[y2] = x2
edges2 = []
for (x, y, c) in edges:
	if not root(x) == root(y):
		union(x, y)
		edges2.append((x, y, c))
adjList = [[] for _ in range(N)]
for (x, y, c) in edges2:
	adjList[x].append((y, c))
	adjList[y].append((x, c))
visited = [False] * N
sizes = [-1] * N
costs = [0] * (2 * M)

def dfs(node):
	visited[node] = True
	sizes[node] = 1
	for (adj, dist) in adjList[node]:
		if not visited[adj]:
			dfs(adj)
			sizes[node] += sizes[adj]
			costs[dist] += sizes[adj] * (N - sizes[adj])
dfs(0)
last = 0
for i in range(len(costs) - 1):
	costs[i + 1] += costs[i] // 2
	costs[i] %= 2
	if costs[i] >= 1:
		last = i
print(*reversed(costs[0:last + 1]), sep='')


from sys import stderr
from heapq import heappop, heappush

def read(f):
	return f(input())

def readlist(f):
	return [f(x) for x in input().split()]

def readinto(c, f):
	for (i, x) in enumerate(input().split()):
		c[i] = f(x)

def readgraph(n, m, directed=False):
	ns = [{} for _ in range(n)]
	edge = [0, 0, 1]
	for _ in range(m):
		readinto(edge, int)
		(u, v, w) = edge
		ns[u - 1][v - 1] = w
		if not directed:
			ns[v - 1][u - 1] = w
	return ns
(N, M) = readlist(int)
components = list(range(N))
V = [set() for _ in range(N)]
E = [None] * M

def getComponent(v):
	u = components[v]
	while u != v:
		w = components[u]
		components[v] = w
		v = u
		u = w
	return u
for _ in range(M):
	(u, v, c) = readlist(int)
	E[c] = (u - 1, v - 1)
for c in range(M):
	(u, v) = E[c]
	tu = getComponent(u)
	tv = getComponent(v)
	if tu != tv:
		components[v] = tu
		components[tv] = tu
		V[u].add(c)
		V[v].add(c)
F = {}
S = [1] * N
leaves = [v for v in range(N) if len(V[v]) == 1]
while leaves:
	v = leaves.pop()
	for c in V[v]:
		(u, w) = E[c]
		u = u + w - v
		F[c] = v
		S[u] += S[v]
		V[u].remove(c)
		if len(V[u]) == 1:
			leaves.append(u)
ans = 0
for (c, v) in F.items():
	n1 = S[v]
	n2 = N - n1
	ans += n1 * n2 << c
print('{0:b}'.format(ans))


from collections import deque, defaultdict
import sys, time
(N, M) = [int(s) for s in input().strip().split()]
CBA = [None] * M
for _ in range(M):
	(A, B, C) = [int(s) for s in input().strip().split()]
	CBA[C] = (B - 1, A - 1)

class NumSet(object):

	def __init__(self, M):
		self.parent = list(range(N))
		self.rank = [0] * N

	def find(self, i):
		if self.parent[i] != i:
			p = i
			while p != self.parent[p]:
				p = self.parent[p]
			while i != p:
				(i, self.parent[i]) = (self.parent[i], p)
		return i

	def union(self, i, j):
		iroot = self.find(i)
		jroot = self.find(j)
		if iroot == jroot:
			return False
		else:
			(irank, jrank) = (self.rank[iroot], self.rank[jroot])
			if irank < jrank:
				self.parent[iroot] = jroot
			elif jrank < irank:
				self.parent[jroot] = iroot
			else:
				self.parent[jroot] = iroot
				self.rank[iroot] += 1
			return True

def make_tree():
	subgraphs = N
	numset = NumSet(M)
	ABC = [[] for _ in range(N)]
	for (C, (B, A)) in enumerate(CBA):
		if subgraphs == 1:
			break
		if numset.union(B, A):
			ABC[A].append((B, C))
			ABC[B].append((A, C))
			subgraphs -= 1
	assert subgraphs == 1
	return ABC

def find_routes_dfs():
	stack = []
	(a, bt) = (0, -1)
	(myx, myy, myn) = (0, 0, 1)
	(yynv_ac, n_ac) = (0, 0)
	i = 0
	seen = [False] * N
	while True:
		if i == len(ABC[a]):
			if not stack:
				break
			(xx, yy, nn) = (myx, myy, myn)
			(a, bt, myx, myy, myn, yynv_ac, n_ac, i, v) = stack.pop()
			nv = nn << v
			yynv = yy + nv
			myx += xx + yynv
			myy += yynv
			myn += nn
			myx += yynv_ac * nn + n_ac * (yy + nv)
			yynv_ac += yynv
			n_ac += nn
		else:
			(b, v) = ABC[a][i]
			i += 1
			if b != bt:
				assert not seen[b]
				seen[b] = True
				if len(ABC[b]) == 0:
					myx += yynv_ac
					myn += 1
					n_ac += 1
				else:
					stack.append((a, bt, myx, myy, myn, yynv_ac, n_ac, i, v))
					(a, bt) = (b, a)
					(myx, myy, myn) = (0, 0, 1)
					(yynv_ac, n_ac) = (0, 0)
					i = 0
	return myx
ABC = make_tree()
s = find_routes_dfs()
print('{0:b}'.format(s))


import sys
[N, M] = [int(x) for x in input().strip().split(' ')]
G = [[] for _ in range(0, N)]
parent = [(-1, 1)] * N
sys.setrecursionlimit(M + 1000)

def root(x):
	next = parent[x]
	while next[0] != -1:
		x = next[0]
		next = parent[next[0]]
	return x

def connect(a, b, d):
	(ra, rb) = (root(a), root(b))
	if ra != rb:
		(pa, pb) = (parent[ra][1], parent[rb][1])
		if pa > pb:
			parent[rb] = (ra, pb)
			parent[ra] = (-1, pa + pb)
		else:
			parent[ra] = (rb, pa)
			parent[rb] = (-1, pa + pb)
		G[a].append((b, d))
		G[b].append((a, d))

def bin_sum_dist():
	visited = [False] * N

	def sum_dist(x):
		visited[x] = True
		(n, sum_d_root, tot) = (1, 0, 0)
		for (y, d) in G[x]:
			if not visited[y]:
				(ny, sum_d_rooty, toty) = sum_dist(y)
				(n, sum_d_root, tot) = (n + ny, sum_d_root + sum_d_rooty + (ny << d), tot + toty + (sum_d_root * ny + sum_d_rooty * n + (n * ny << d)))
		return (n, sum_d_root, tot)
	return bin(sum_dist(0)[2])[2:]

def job():
	road = [(0, 0)] * M
	for _ in range(0, M):
		[a, b, d] = [int(x) for x in input().strip().split(' ')]
		road[d] = (a - 1, b - 1)
	for d in range(0, M):
		(a, b) = road[d]
		connect(a, b, d)
	print(bin_sum_dist())
job()


import heapq
(N, M) = map(int, input().split())
graph = [[] for i in range(N + 1)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	graph[a].append((c, b))
	graph[b].append((c, a))
children = [None] * (N + 1)
children[0] = []
active = [(0, 1, 0)]
while active:
	(c, i, p) = heapq.heappop(active)
	if children[i] != None:
		continue
	children[i] = []
	children[p].append((c, i))
	for (c, j) in graph[i]:
		if children[j] == None:
			heapq.heappush(active, (c, j, i))
graph = None
active = [1]
first = [1] * (N + 1)
ndesc = [0] * (N + 1)
dist = [0] * (N + 1)
total = 0
while active:
	i = active[-1]
	if first[i]:
		first[i] = 0
		for (c, j) in children[i]:
			active.append(j)
	else:
		active.pop()
		n = 1
		d = 0
		for (c, j) in children[i]:
			s = dist[j] + (ndesc[j] << c)
			total += d * ndesc[j] + s * n
			d += s
			n += ndesc[j]
			dist[j] = 0
		ndesc[i] = n
		dist[i] = d
print(bin(total)[2:])


import time
import sys
t0 = time.time()

class PQueue(object):

	def __init__(self, ids, priorities):
		self.A = list(ids)
		self.P = dict(((ids[i], priorities[i]) for i in range(len(priorities))))
		self.size = len(self.A)
		if self.size != len(self.P):
			raise Exception('PQueue: ids and priorities must have the same length')
		self.L = dict(((self.A[i], i) for i in range(self.size)))
		for i in range(self.size // 2 - 1, -1, -1):
			self.__min_heapify(i)

	def __min_heapify(self, i):
		while True:
			(l, r) = (2 * i + 1, 2 * i + 2)
			smallest = i
			if l < self.size and self.P[self.A[l]] < self.P[self.A[smallest]]:
				smallest = l
			if r < self.size and self.P[self.A[r]] < self.P[self.A[smallest]]:
				smallest = r
			if smallest != i:
				(self.A[i], self.A[smallest]) = (self.A[smallest], self.A[i])
				self.L[self.A[i]] = i
				self.L[self.A[smallest]] = smallest
				i = smallest
			else:
				break

	def empty(self):
		return self.size == 0

	def pop_min(self):
		if self.size < 1:
			raise Exception('PQueue: Cannot pop from empty queue')
		min_id = self.A[0]
		self.L.pop(min_id)
		self.A[0] = self.A[-1]
		self.L[self.A[0]] = 0
		self.A.pop()
		self.size -= 1
		self.__min_heapify(0)
		return min_id

	def decrease_priority(self, id, priority):
		if self.P[id] < priority:
			raise Exception('PQueue: new key is bigger than old key')
		self.P[id] = priority
		i = self.L[id]
		parent = (i - 1) // 2
		while i > 0 and self.P[self.A[i]] < self.P[self.A[parent]]:
			(self.A[i], self.A[parent]) = (self.A[parent], self.A[i])
			self.L[self.A[i]] = i
			self.L[self.A[parent]] = parent
			i = parent
			parent = (i - 1) // 2
t1 = time.time()
print('Read PQueue class:', '%f' % (t1 - t0), file=sys.stderr)
t0 = t1
(N, M) = [int(inp) for inp in input().strip().split(' ')]
V = {}
Adj = dict(((v, set()) for v in range(1, N + 1)))
for i in range(M):
	(Ai, Bi, Ci) = [int(inp) for inp in input().strip().split(' ')]
	T = (Ai, Bi) if Ai < Bi else (Bi, Ai)
	if T in V:
		V[T] = min(V[T], Ci)
	else:
		V[T] = Ci
	Adj[Ai].add(Bi)
	Adj[Bi].add(Ai)
t1 = time.time()
print('Initialize graph:', '%f' % (t1 - t0), file=sys.stderr)
t0 = t1
D = dict(zip(range(1, N + 1), [0 if v == 1 else float('inf') for v in range(1, N + 1)]))
P = {}
children = dict(((v, set()) for v in range(1, N + 1)))
Q = PQueue(range(1, N + 1), [0 if v == 1 else float('inf') for v in range(1, N + 1)])
while not Q.empty():
	u = Q.pop_min()
	if u in P:
		children[P[u]].add(u)
	for v in Adj[u]:
		Adj[v].remove(u)
		T = (u, v) if u < v else (v, u)
		if D[v] > V[T]:
			D[v] = V[T]
			Q.decrease_priority(v, V[T])
			P[v] = u
t1 = time.time()
print('Djikstra:', '%f' % (t1 - t0), file=sys.stderr)
t0 = t1
answer = 0
below = {}
Q = [1]
seen = set()
while Q:
	v = Q[-1]
	if v in seen:
		if v in P:
			below_v = 1
			for u in children[v]:
				below_v += below[u]
			below[v] = below_v
			u = P[v]
			T = (u, v) if u < v else (v, u)
			answer += below_v * (N - below_v) << V[T]
		Q.pop()
	else:
		seen.add(v)
		Q.extend(children[v])
t1 = time.time()
print('Traverse Tree:', '%f' % (t1 - t0), file=sys.stderr)
t0 = t1
print(bin(answer)[2:])


from queue import PriorityQueue

def main():
	(N, E) = readints()
	tree_edges = []
	tree_edges_multiplier = []
	pq = PriorityQueue()
	graph = Graph()
	visited = {}
	tree = {}
	descendents_count = {}
	for v in range(0, N):
		tree[v] = []
		descendents_count[v] = 0
		graph.insertVertex(v)
	for i in range(0, E):
		(a, b, dis) = readints()
		a = a - 1
		b = b - 1
		edge = Edge(a, b, dis)
		graph.insertEdge(a, b, edge)
	visited[0] = None
	for edge in graph.incident_edges(0):
		pq.put((edge.weight(), (0, edge)))
	while not pq.empty():
		(key, value) = pq.get()
		(u, edge) = value
		v = edge.opposite(u)
		if v not in visited:
			visited[v] = edge
			tree_edges.append(Edge(u, v, edge.weight()))
			tree[u].append(v)
			for link in graph.incident_edges(v):
				w = link.opposite(v)
				if w not in visited:
					pq.put((link.weight(), (v, link)))
	totalcount = count_descendents(tree, 0, descendents_count)
	binary = Binary()
	for edge in tree_edges:
		multiplier = descendents_count[edge._v] * (N - descendents_count[edge._v])
		tree_edges_multiplier.append(multiplier)
		bits = [int(x) for x in bin(multiplier)[2:]]
		bits.reverse()
		for i in range(0, len(bits)):
			if bits[i] == 1:
				binary.put(i + edge.weight())
	binary._data.reverse()
	for x in binary._data:
		print(x, end='')
	print('', end='\n')

def count_descendents(tree, index, descendents_count):
	count = 1
	for child in tree[index]:
		count += count_descendents(tree, child, descendents_count)
	descendents_count[index] = count
	return count

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

class Edge:

	def __init__(self, u, v, d):
		self._u = u
		self._v = v
		self._distance = d

	def opposite(self, u):
		return self._v if u == self._u else self._u

	def weight(self):
		return self._distance

	def print(self):
		print(self._u, self._v, self._distance)

class Graph:

	def __init__(self, directed=False):
		self._outgoing = {}
		self._incoming = {} if directed else self._outgoing

	def insertVertex(self, index):
		self._outgoing[index] = {}
		self._incoming[index] = {}

	def insertEdge(self, u, v, edge):
		if v not in self._outgoing[u]:
			self._outgoing[u][v] = edge
			self._incoming[v][u] = edge
		else:
			old_edge = self._outgoing[u][v]
			if edge.weight() < old_edge.weight():
				self._outgoing[u][v] = edge
				self._incoming[v][u] = edge

	def incident_edges(self, v, outgoing=True):
		adj = self._outgoing if outgoing else self._incoming
		for edge in adj[v].values():
			yield edge

class Binary:

	def __init__(self):
		self._data = []

	def put(self, position):
		while len(self._data) <= position:
			self._data.append(0)
		if self._data[position] == 0:
			self._data[position] = 1
		else:
			self._data[position] = 0
			self.put(position + 1)
main()


import sys
import heapq
from functools import reduce
INF = 999999999999999

def prims_mst_wt(g, start):
	vn = g[0][0]
	inTree = dict()
	tree = [[] for x in range(vn + 1)]
	vlist = g[1]
	inTree[start] = True
	edge_heap = [(wt, adj, start) for (adj, wt) in vlist[start]]
	heapq.heapify(edge_heap)
	for x in range(g[0][0]):
		minV = 0
		try:
			while True:
				(minWt, minV, camefrom) = heapq.heappop(edge_heap)
				try:
					inTree[minV]
				except KeyError:
					break
		except IndexError:
			break
		inTree[minV] = True
		tree[camefrom].append((minV, minWt))
		tree[minV].append((camefrom, minWt))
		for (child, wt) in vlist[minV]:
			if child not in inTree:
				heapq.heappush(edge_heap, (wt, child, minV))
	print('done mst', file=sys.stderr)
	return tree

def count_uses(mst):
	start = 1
	visited = [False for x in range(len(mst))]
	subtr_sz = [[(0, 0)] for x in range(len(mst))]
	stack = [(start, 0, -1, -1)]
	visited[start] = True
	while len(stack) != 0:
		(popd, depth, pindex, chnumber) = stack[-1]
		alldone = True
		for (cn, tmp) in enumerate(mst[popd]):
			(child, wt) = tmp
			if not visited[child]:
				stack.append((child, depth + 1, popd, cn))
				visited[child] = True
				alldone = False
		if alldone:
			stack.pop()
			if pindex == -1:
				break
			subtr_sz[pindex].append((reduce(lambda a, b: a + b, map(lambda x: x[0], subtr_sz[popd])) + 1, mst[pindex][chnumber][1]))
	print('done', file=sys.stderr)
	tot = 0
	vn = len(mst) - 1
	for vtex in subtr_sz:
		for subtr in vtex:
			(sz, wt) = subtr
			tot += (vn - sz) * sz * (1 << wt)
	print(bin(tot)[2:])

def main():
	li = []
	(v, e) = map(int, input().strip().split())
	li.append([v, e])
	li.append([])
	for j in range(v + 1):
		li[1].append([])
	vlist = li[1]
	for j in range(e):
		tmp_li = list(map(lambda x: int(x), input().strip().split()))
		alreadyThere = False
		try:
			for (i, x) in enumerate(vlist[tmp_li[0]]):
				if x[0] == tmp_li[1]:
					if x[1] > tmp_li[2]:
						vlist[tmp_li[0]][i][1] = tmp_li[2]
						alreadyThere = True
						break
			for (i, x) in enumerate(vlist[tmp_li[1]]):
				if x[0] == tmp_li[0]:
					if x[1] > tmp_li[2]:
						vlist[tmp_li[1]][i][1] = tmp_li[2]
						break
			if not alreadyThere:
				vlist[tmp_li[0]].append([tmp_li[1], tmp_li[2]])
				vlist[tmp_li[1]].append([tmp_li[0], tmp_li[2]])
		except IndexError:
			vlist[tmp_li[0]].append([tmp_li[1], tmp_li[2]])
			vlist[tmp_li[1]].append([tmp_li[0], tmp_li[2]])
	print('done input', file=sys.stderr)
	mst = prims_mst_wt(li, 1)
	count_uses(mst)
main()


from operator import itemgetter
(n, m) = list(map(int, input().split()))
edges = []
for _ in range(m):
	(a, b, c) = list(map(int, input().split()))
	edges.append([a - 1, b - 1, c])
edges.sort(key=itemgetter(2))
minSpanTree = []
subGraphs = list(range(n))
componentSize = []
for i in range(n):
	minSpanTree.append({})
	componentSize.append(1)

def findRoot(n):
	while subGraphs[n] != n:
		n = subGraphs[n]
	return n
minEdgeCnt = 0
for e in edges:
	r1 = findRoot(e[0])
	r2 = findRoot(e[1])
	if r1 != r2:
		if componentSize[r1] < componentSize[r2]:
			(r1, r2) = (r2, r1)
		(subGraphs[r2], subGraphs[e[0]], subGraphs[e[1]]) = [r1] * 3
		componentSize[r1] += componentSize[r2]
		minSpanTree[e[0]][e[1]] = e[2]
		minSpanTree[e[1]][e[0]] = e[2]
		minEdgeCnt += 1
		if minEdgeCnt == n - 1:
			break
ans = [0]
visited = set()

def countKids(node):
	visited.add(node)
	kids = 1
	for e in minSpanTree[node]:
		if e not in visited:
			eKids = countKids(e)
			ans[0] += (n - eKids) * eKids * (1 << minSpanTree[node][e])
			kids += eKids
	return kids
countKids(0)
print(bin(ans[0])[2:])


def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def unite(parent, weight, i, j):
	(ip, jp) = (find(parent, i), find(parent, j))
	if ip == jp:
		return False
	if weight[ip] < weight[jp]:
		parent[ip] = jp
		weight[jp] += weight[ip]
	else:
		parent[jp] = ip
		weight[ip] += weight[jp]
	return True

def dfs(graph):
	size = [0 for _ in range(len(graph))]
	ans = 0

	def dfs(s, p):
		nonlocal ans
		size[s] = 1
		for (t, c) in graph[s]:
			if t == p:
				continue
			dfs(t, s)
			size[s] += size[t]
			ans += size[t] * (len(graph) - size[t]) << c
	dfs(0, -1)
	return ans
(N, M) = map(int, input().split())
edges = sorted((tuple(map(int, input().split())) for _ in range(M)), key=lambda t: t[2])
parent = [i for i in range(N)]
weight = [1 for _ in range(N)]
graph = [[] for _ in range(N)]
for (u, v, c) in edges:
	if not unite(parent, weight, u - 1, v - 1):
		continue
	graph[u - 1].append((v - 1, c))
	graph[v - 1].append((u - 1, c))
print('{:b}'.format(dfs(graph)))


(N, M) = [int(x) for x in input().strip().split(' ')]
G = []
for _ in range(M):
	(a, b, c) = [int(x) for x in input().strip().split(' ')]
	G.append((c, a - 1, b - 1))
G = sorted(G)
C = [i for i in range(N)]
S = [1 for i in range(N)]

def find(C, S, u):
	if C[u] != u:
		C[u] = find(C, S, C[u])
	return C[u]

def union(C, S, u, v):
	cu = find(C, S, u)
	cv = find(C, S, v)
	if cu == cv:
		return False
	if S[cu] >= S[cv]:
		S[cu] += S[cv]
		S[cv] = 0
		C[cv] = cu
	else:
		S[cv] += S[cu]
		S[cv] = 0
		C[cu] = cv
	return True
H = [[] for i in range(N)]
for (c, a, b) in G:
	if union(C, S, a, b):
		H[a].append((b, c))
		H[b].append((a, c))

def add(A, B):
	for (k, v) in B.items():
		A[k] = A.get(k, 0) + v

def dfs(H, M, u):
	M[u] = True
	C = {}
	count = 1
	for (v, c) in H[u]:
		if M[v]:
			continue
		(C1, count1) = dfs(H, M, v)
		add(C, C1)
		C[c] = C.get(c, 0) + count1 * (N - count1)
		count += count1
	return (C, count)
C = {}
V = [False] * N
for i in range(N):
	if not V[i]:
		(C1, count1) = dfs(H, V, i)
		add(C, C1)
B = []
m = max(C.keys())
i = 0
while i <= m:
	if i not in C:
		B.append(0)
	count = C[i]
	C[i + 1] = C.get(i + 1, 0) + count // 2
	B.append(count % 2)
	if i == m and C[i + 1] > 0:
		m += 1
	i += 1
print(*reversed(B), sep='')


import collections

class UF(object):

	def __init__(self, N):
		(self.parent, self.size) = ([], [])
		for i in range(N):
			self.parent.append(i)
			self.size.append(1)

	def root(self, n):
		while self.parent[n] != n:
			np = self.parent[n]
			self.parent[n] = self.parent[np]
			n = np
		return n

	def connected(self, n1, n2):
		return self.root(n1 - 1) == self.root(n2 - 1)

	def union(self, n1, n2):
		root1 = self.root(n1 - 1)
		root2 = self.root(n2 - 1)
		if root1 == root2:
			return
		if self.size[root1] > self.size[root2]:
			self.parent[root2] = root1
		else:
			self.parent[root1] = root2

class DFS(object):

	def __init__(self, N, M, graph):
		self.N = N
		self.graph = graph
		self.visited = [False] * N
		self.size = [0] * N
		self.edgesPower = [0] * M

	def visit(self, n):
		self.visited[n - 1] = True

	def isVisited(self, n):
		return self.visited[n - 1]

	def dfs(self, n):
		if self.isVisited(n):
			return
		self.visit(n)
		for (w, a, b) in self.graph[n]:
			o = a if n != a else b
			if not self.isVisited(o):
				self.dfs(o)
				s = self.size[o - 1] + 1
				self.size[n - 1] += s
				self.edgesPower[w] += (self.N - s) * s

def main():
	(N, M) = map(int, input().split())
	edges = []
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		edges.append((c, a, b))
	uf = UF(N)
	edges.sort()
	mst = collections.defaultdict(lambda : [])
	for e in edges:
		(_, a, b) = e
		if not uf.connected(a, b):
			uf.union(a, b)
			mst[a].append(e)
			mst[b].append(e)
	dfs = DFS(N, M, mst)
	dfs.dfs(1)
	r = 0
	for (i, c) in enumerate(dfs.edgesPower):
		r += c * (1 << i)
	print('{0:b}'.format(r))
main()


import sys
import heapq
import math
from collections import defaultdict

def add_edge(edge, graph):
	(l, c1, c2) = edge
	graph[c1][c2] = min(l, graph[c1][c2])
	graph[c2][c1] = min(l, graph[c2][c1])

def add_neighbors(city, graph, heap):
	for c2 in graph[city].keys():
		l = graph[city][c2]
		heapq.heappush(heap, (l, city, c2))

def find_leaves(graph):
	leaves = []
	for (i, dic) in enumerate(graph):
		if len(dic.keys()) == 1:
			leaves.append(i)
	return leaves
(n_cities, n_roads) = map(int, input().split(' '))
full_graph = [defaultdict(lambda : float('inf')) for i in range(n_cities)]
min_edge = (float('inf'), -1, -1)
for line in sys.stdin:
	(c1, c2, l) = map(int, line.split(' '))
	add_edge((l, c1 - 1, c2 - 1), full_graph)
	if l < min_edge[0]:
		min_edge = (l, c1 - 1, c2 - 1)
reduced_graph = [defaultdict(lambda : float('inf')) for i in range(n_cities)]
visited = {}
heap = []
visited[min_edge[1]] = True
visited[min_edge[2]] = True
add_edge(min_edge, reduced_graph)
add_neighbors(min_edge[1], full_graph, heap)
add_neighbors(min_edge[2], full_graph, heap)
n_edges_added = 1
while n_edges_added < n_cities - 1:
	(l, c1, c2) = heapq.heappop(heap)
	if c1 not in visited or c2 not in visited:
		visited[c1] = True
		visited[c2] = True
		n_edges_added += 1
		add_edge((l, c1, c2), reduced_graph)
		add_neighbors(c1, full_graph, heap)
		add_neighbors(c2, full_graph, heap)
n_removed = 0
s = 0
leaves = find_leaves(reduced_graph)
counts = defaultdict(lambda : 1)
bits = defaultdict(int)
while n_removed < n_cities - 1:
	new_leaves = []
	for leaf in leaves:
		n_removed += 1
		for c in reduced_graph[leaf].keys():
			del reduced_graph[c][leaf]
			l = reduced_graph[leaf][c]
			bits[l] = counts[leaf] * (n_cities - counts[leaf])
			counts[c] += counts[leaf]
			if len(reduced_graph[c].keys()) == 1:
				new_leaves.append(c)
	leaves = new_leaves
done = False
while not done:
	done = True
	keys = list(bits.keys())
	for k in keys:
		if bits[k] == 0:
			continue
		shift = math.log(bits[k], 2)
		if shift >= 1:
			bits[int(shift) + k] += 1
			bits[k] = bits[k] - 2 ** int(shift)
			done = False
max_bit = max(bits.keys())
l = ['0'] * (max_bit + 1)
for k in bits.keys():
	if bits[k] == 1:
		l[k] = '1'
print(''.join(l)[::-1])


p = list(range(10 ** 5))

def dsu_get(v):
	if p[v] != v:
		p[v] = dsu_get(p[v])
	return p[v]

def dsu_merge(u, v):
	u = dsu_get(u)
	v = dsu_get(v)
	p[u] = v
	return u != v
(n, m) = map(int, input().split())
e = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	e += [(c, b - 1, a - 1)]
e.sort()
G = [[] for x in range(n)]
for (c, a, b) in e:
	if dsu_merge(a, b):
		G[a] += [(b, c)]
		G[b] += [(a, c)]
f = [0] * m

def dfs(v, par=-1):
	sz = 1
	for (u, c) in G[v]:
		if u == par:
			continue
		y = dfs(u, v)
		f[c] = y * (n - y)
		sz += y
	return sz
dfs(0)
ans = 0
for x in f[::-1]:
	ans *= 2
	ans += x
print(bin(ans)[2:])


from heapq import heappush, heappop, heapify

def lstin():
	return list(map(int, input().strip().split()))
(N, M) = lstin()
dag = [list() for _ in range(N + 1)]
distances = dict()

def hash(u, v):
	return (u, v) if u < v else (v, u)

def prim():
	edges = [list() for _ in range(N + 1)]
	for _ in range(M):
		(u, v, c) = lstin()
		edges[u].append(v)
		edges[v].append(u)
		uv = hash(u, v)
		distances[uv] = min(distances.get(uv, float('inf')), c)
	root = 1
	visited = [False for _ in edges]
	pq = [(distances[hash(root, u)], u, root) for u in edges[root]]
	heapify(pq)
	visited[root] = True
	while pq:
		(d, v, u) = heappop(pq)
		if not visited[v]:
			dag[u].append(v)
			visited[v] = True
			for w in edges[v]:
				if not visited[w]:
					heappush(pq, (distances[hash(v, w)], w, v))

def flatten_postorder_traversal():
	root = 1
	stack = [(root, v) for v in dag[root]]
	flatten = list()
	while stack:
		(u, v) = stack.pop()
		flatten.append((u, v))
		stack.extend(((v, w) for w in dag[v] if w != u))
	flatten.reverse()
	return flatten
prim()
res = 0
descendants = [1] * (N + 1)
for (u, v) in flatten_postorder_traversal():
	res += (1 << distances[hash(u, v)]) * (N - descendants[v]) * descendants[v]
	descendants[u] += descendants[v]
print(bin(res)[2:])


import sys
sys.setrecursionlimit(30000)
import heapq
(n, m) = [int(s) for s in input().split(' ')]
edges = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = [int(s) for s in input().split(' ')]
	edges[a - 1].append((c, b - 1))
	edges[b - 1].append((c, a - 1))

def search_min_sum(edges, n, v):
	dist = [0 for i in range(n)]
	used = set([v])
	hp = []
	for e in edges[v]:
		heapq.heappush(hp, (e[0], e[1], v))
	while len(hp) > 0:
		(di, vi, v_from) = heapq.heappop(hp)
		if vi in used:
			continue
		used.add(vi)
		dist[vi] = di
		if len(edges[vi]) == 0:
			continue
		while len(edges[vi]) > 0:
			e = heapq.heappop(edges[vi])
			if e[1] in used:
				continue
			heapq.heappush(hp, (e[0] + di, e[1], vi))
	dist_sum = sum(dist[v + 1:])
	return dist_sum
	pass

def copy_edges(edges):
	return [list(e) for e in edges]

def print_res(min_dist_sum_all):
	res_str = []
	while min_dist_sum_all > 0:
		ost = min_dist_sum_all % 2
		res_str.append(str(ost))
		min_dist_sum_all //= 2
	if len(res_str) == 0:
		print('0')
	else:
		for i in range(len(res_str) - 1, -1, -1):
			sys.stdout.write(res_str[i])

def solve_dijkstra(edges, n):
	min_dist_sum_all = 0
	for i in range(n - 1):
		min_dist_sum = search_min_sum(copy_edges(edges), n, i)
		min_dist_sum_all += min_dist_sum
	print(min_dist_sum_all)
	print_res(min_dist_sum_all)

def dfs(edges, n, v, v_from, d, used, dxv, res):
	if used[v]:
		return
	used[v] = True
	for (di, vi) in edges[v]:
		if used[vi]:
			continue
		dfs(edges, n, vi, v, di, used, dxv, res)
	sum_add = dxv[v] * (n - dxv[v]) * d
	dxv[v_from] += dxv[v]
	res[0] += sum_add

def dfs_flat(mst, n, v_start, used, dxv):
	used[v_start] = True
	(di, vi) = mst[v_start][0]
	st = [(v_start, vi, di)]
	sum_all = 0
	while len(st) > 0:
		has_new = False
		(v_from, v_to, d) = st[-1]
		if not used[v_to]:
			for (di, vi) in mst[v_to]:
				if used[vi]:
					continue
				has_new = True
				st.append((v_to, vi, di))
		used[v_to] = True
		if has_new:
			continue
		del st[-1]
		d = 1 << d
		sum_add = dxv[v_to] * (n - dxv[v_to]) * d
		sum_all += sum_add
		dxv[v_from] += dxv[v_to]
	return sum_all

def mst_prim(edges, n):
	mst = [[] for i in range(n)]
	start_v = 0
	used = [False] * n
	used[start_v] = True
	used_count = 1
	hp = []
	for (di, vi) in edges[start_v]:
		heapq.heappush(hp, (di, start_v, vi))
	while used_count < n and len(hp) > 0:
		(d, v_from, v_to) = heapq.heappop(hp)
		if used[v_from] and used[v_to]:
			continue
		if not used[v_from]:
			used[v_from] = True
			used_count += 1
			for (di, vi) in edges[v_from]:
				if not used[vi]:
					heapq.heappush(hp, (di, v_from, vi))
		else:
			used[v_to] = True
			used_count += 1
			for (di, vi) in edges[v_to]:
				if not used[vi]:
					heapq.heappush(hp, (di, v_to, vi))
		mst[v_from].append((d, v_to))
		mst[v_to].append((d, v_from))
	return mst

def solve_counting(edges, n):
	mst = mst_prim(edges, n)
	dxv = [1] * n
	used = [False] * n
	res = [0]
	v_from = 0
	while v_from < n and len(mst[v_from]) > 1:
		v_from += 1
	used[v_from] = True
	sum_all = dfs_flat(mst, n, v_from, used, dxv)
	print('{0:b}'.format(sum_all))
	return
	(di, v_to) = mst[v_from][0]
	dfs(mst, n, v_to, v_from, di, used, dxv, res)
	print_res(res[0])
solve_counting(edges, n)


p = list(range(10 ** 5))

def dsu_get(v):
	if p[v] != v:
		p[v] = dsu_get(p[v])
	return p[v]

def dsu_merge(u, v):
	u = dsu_get(u)
	v = dsu_get(v)
	p[u] = v
	return u != v
(n, m) = map(int, input().split())
e = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	e += [(c, b - 1, a - 1)]
e.sort()
G = [[] for x in range(n)]
for (c, a, b) in e:
	if dsu_merge(a, b):
		G[a] += [(b, c)]
		G[b] += [(a, c)]
f = [0] * m

def dfs(v, par=-1):
	sz = 1
	for (u, c) in G[v]:
		if u == par:
			continue
		y = dfs(u, v)
		f[c] = y * (n - y)
		sz += y
	return sz
dfs(0)
ans = 0
for x in f[::-1]:
	ans *= 2
	ans += x
print(bin(ans)[2:])


class DisjointSet(object):

	def __init__(self, nr_elements):
		self.parent = list(range(nr_elements))
		self.rank = [0] * nr_elements

	def same(self, e1, e2):
		return self.find(e1) == self.find(e2)

	def find(self, element):
		curr = element
		path = list()
		while self.parent[curr] != curr:
			path.append(curr)
			curr = self.parent[curr]
		for x in path:
			self.parent[x] = curr
		return self.parent[element]

	def merge(self, e1, e2):
		(r1, r2) = (self.find(e1), self.find(e2))
		if r1 == r2:
			return
		if self.rank[r1] < self.rank[r2]:
			self.parent[r1] = r2
		elif self.rank[r1] > self.rank[r2]:
			self.parent[r2] = r1
		else:
			self.parent[r1] = r2
			self.rank[r2] += 1
(n, m) = map(int, input().split())
edges = list()
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((c, a - 1, b - 1))
ds = DisjointSet(n)
adj = {x: dict() for x in range(n)}
for (c, a, b) in sorted(edges):
	if not ds.same(a, b):
		ds.merge(a, b)
		adj[a][b] = c
		adj[b][a] = c
parent = {x: 0 for x in range(n)}
depth = {x: 0 for x in range(n)}
stack = [0]
while len(stack):
	curr = stack.pop()
	curr_d = depth[curr]
	for nei in adj[curr]:
		if nei != parent[curr]:
			parent[nei] = curr
			depth[nei] = curr_d + 1
			stack.append(nei)
nodes = sorted(list(range(n)), key=lambda x: depth[x], reverse=True)
num_descendants = {x: 0 for x in range(n)}
from collections import defaultdict
bits = defaultdict(int)

def add_one(bits, pos):
	if bits[pos] == 0:
		bits[pos] = 1
		return
	bits[pos] = 0
	add_one(bits, pos + 1)
for x in nodes:
	p = parent[x]
	if p != x:
		num_descendants[p] += num_descendants[x] + 1
		side_1 = num_descendants[x] + 1
		side_2 = n - side_1
		exp = adj[x][p]
		new_bits = bin(side_1 * side_2)[2:]
		for i in range(len(new_bits)):
			if new_bits[-i - 1] == '1':
				add_one(bits, i + exp)
max_bit = max(bits.keys())
number = ''.join((str(bits[b]) for b in reversed(range(max_bit + 1))))
print(number)


import random
(N, M) = map(int, input().split())
edges = []

def find(x):
	q = []
	while x != parent[x]:
		q.append(x)
		x = parent[x]
	for val in q:
		parent[val] = x
	return x

def union(x, y):
	px = find(x)
	py = find(y)
	if px == py:
		return False
	if random.random() < 0.5:
		parent[px] = py
	else:
		parent[py] = px
	return True

def explore(root):
	q = [root]
	count = [-1 for i in range(N)]
	up = [-1 for i in range(N)]
	st = 0
	while st < len(q):
		node = q[st]
		count[node] = 0
		for (neigh, c) in span[node]:
			if count[neigh] == -1:
				up[neigh] = node
				q.append(neigh)
		st += 1
	for i in range(len(q) - 1, 0, -1):
		node = q[i]
		count[up[node]] += count[node] + 1
	st = 0
	q = [root]
	up = [-1 for i in range(N)]
	while st < len(q):
		node = q[st]
		up[node] = 0
		for (neigh, c) in span[node]:
			if up[neigh] == -1:
				q.append(neigh)
				tot_cost[c] += (count[neigh] + 1) * (N - count[neigh] - 1)
		st += 1
for _ in range(M):
	(A, B, C) = map(int, input().split())
	edges.append((C, A - 1, B - 1))
edges.sort()
parent = [i for i in range(N)]
span = [[] for i in range(N)]
for (C, A, B) in edges:
	cost = 0
	if union(A, B):
		span[A].append((B, C))
		span[B].append((A, C))
tot_cost = [0 for i in range(M)]
explore(0)
sol = []
for i in range(M - 1):
	tot_cost[i + 1] += tot_cost[i] // 2
	tot_cost[i] = tot_cost[i] % 2
	sol.append(tot_cost[i])
carry = tot_cost[M - 1]
while carry > 0:
	if carry % 2 == 1:
		sol.append(1)
	else:
		sol.append(0)
	carry = carry // 2
sol.reverse()
canPrint = False
for val in sol:
	if val == 1:
		canPrint = True
	if canPrint:
		print(val, end='')
print()


def depthFirstSearch(v, par=-1):
	depth = 1
	for (u, c) in G[v]:
		if u == par:
			continue
		y = depthFirstSearch(u, v)
		f[c] = y * (n - y)
		depth += y
	return depth

def value_retrieve(val):
	if arbList[val] != val:
		arbList[val] = value_retrieve(arbList[val])
	return arbList[val]

def merge_in(u, v):
	u = value_retrieve(u)
	v = value_retrieve(v)
	arbList[u] = v
	return u != v
arbList = list(range(10 ** 7))
(n, m) = map(int, input().split())
e = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	e += [(c, b - 1, a - 1)]
e.sort()
G = [[] for x in range(n)]
for (c, a, b) in e:
	if merge_in(a, b):
		G[a] += [(b, c)]
		G[b] += [(a, c)]
f = [0] * m
depthFirstSearch(0)
ans = 0
for x in f[::-1]:
	ans *= 2
	ans += x
binary_conversion = bin(ans)[2:]
print(binary_conversion)


(N, M) = map(int, input().split(' '))
(V, E, MT) = ([[i, i, [], None] for i in range(N + 1)], sorted([tuple(map(int, input().split(' '))) for _ in range(M)], key=lambda x: x[2]), 0)

def getGid(x):
	y = x
	while V[y][1] != y:
		y = V[y][1]
	while V[x][1] != y:
		(x, V[x][1]) = (V[x][1], y)
	return y
(M, Q) = (0, [None] * N)
for (a, b, c) in E:
	(ga, gb) = (getGid(a), getGid(b))
	if ga != gb:
		if ga > gb:
			V[ga][1] = gb
		else:
			V[gb][1] = ga
		if c > MT:
			MT = c
		M += 1
		(V[a][2].append((V[b], c)), V[b][2].append((V[a], c)))
		if M == N - 1:
			break
(V[1][3], Q[0], qsi, RS, os) = (V[0], V[1], 1, [0] * (MT + N), '')
for qi in range(N):
	q = Q[qi]
	for (ch, c) in q[2]:
		if not ch[3]:
			(ch[3], Q[qsi], qsi) = (q, ch, qsi + 1)
for v in V:
	v[1] = 1
for q in Q[::-1]:
	q[3][1] += q[1]
	for (ch, c) in q[2]:
		if ch[1] < q[1]:
			RS[c] += (N - ch[1]) * ch[1]
for i in range(MT + N - 1):
	(RS[i], RS[i + 1]) = (RS[i] & 1, RS[i + 1] + (RS[i] >> 1))
for ci in RS[::-1]:
	if os or ci:
		os += str(ci)
print(os)


import sys
from operator import itemgetter

def warn(*args, **kwargs):
	pass

def get_int():
	return int(sys.stdin.readline())

def get_ints():
	return [int(x) for x in sys.stdin.readline().split()]

class UnionFind:

	def __init__(self, size):
		self.link = list(range(size))
		self.size = [1] * size

	def root(self, x):
		while x != self.link[x]:
			self.link[x] = self.link[self.link[x]]
			x = self.link[x]
		return x

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

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			raise ValueError('x and y already in one set')
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.size[x] += self.size[y]
		self.link[y] = x

class WeightedGraph:

	def __init__(self, size):
		self.node = [None] * size
		self.adj = [[] for _ in range(size)]

	def add_edge(self, u, v, weight=0):
		self.adj[u].append((v, weight))
		self.adj[v].append((u, weight))

	def __len__(self):
		return len(self.adj)

def dfs_count(G, u, parent=None):
	G.node[u] = 1
	for (v, _) in G.adj[u]:
		if v == parent:
			continue
		dfs_count(G, v, u)
		G.node[u] += G.node[v]

def total_weight(G, cur_weight, u, parent=None):
	for (v, w) in G.adj[u]:
		if v == parent:
			continue
		n = (G.node[0] - G.node[v]) * G.node[v]
		cur_weight += n * (1 << w)
		cur_weight = total_weight(G, cur_weight, v, u)
	return cur_weight

def main():
	(V, E) = get_ints()
	edges = [None] * E
	for i in range(E):
		(u, v, w) = get_ints()
		edges[i] = (u - 1, v - 1, w)
	edges.sort(key=itemgetter(2))
	s = UnionFind(V)
	G = WeightedGraph(V)
	for (u, v, w) in edges:
		if not s.same(u, v):
			s.unite(u, v)
			G.add_edge(u, v, w)
	sys.setrecursionlimit(100000)
	dfs_count(G, 0)
	warn('subtree counts:', G.node)
	tw = total_weight(G, 0, 0)
	tw_bin = bin(tw)
	print(tw_bin[2:])
main()


import os
import sys
import heapq as hq
import time

def find_other(t, i):
	if i == t[0]:
		return t[1]
	elif i == t[1]:
		return t[0]
	else:
		return None

def roadsInHackerland(n, roads):
	max_cost = 0
	edges_cost = dict()
	MST_neigh = [[0, []] for _ in range(n)]
	added = set([0])
	ws = []
	for (j, dist) in roads[0].items():
		ws.append((dist, 0, j))
	hq.heapify(ws)
	while len(added) < n:
		(dist, a, b) = hq.heappop(ws)
		if a > b:
			(a, b) = (b, a)
		if not a in added:
			i = a
		elif not b in added:
			i = b
		else:
			continue
		edges_cost[a, b] = dist
		if dist > max_cost:
			max_cost = dist
		added.add(i)
		MST_neigh[a][0] += 1
		MST_neigh[b][0] += 1
		MST_neigh[a][1].append((a, b))
		MST_neigh[b][1].append((a, b))
		for (j, dist) in roads[i].items():
			if not j in added:
				hq.heappush(ws, (dist, i, j))
	edges_nodes = dict()
	ws = []
	for (node, item) in enumerate(MST_neigh):
		if item[0] == 1:
			ws.append((node, item))
	while len(ws) > 0:
		(me, item) = ws.pop(0)
		tmp = 1
		unsolved = None
		if item[0] < 1:
			continue
		for edge in item[1]:
			if edge in edges_nodes:
				tmp += edges_nodes[edge][find_other(edge, me)]
			else:
				unsolved = edge
		peer_node = find_other(unsolved, me)
		edges_nodes[unsolved] = {me: tmp, peer_node: n - tmp}
		item[0] -= 1
		MST_neigh[peer_node][0] -= 1
		if MST_neigh[peer_node][0] == 1:
			ws.append((peer_node, MST_neigh[peer_node]))
	res = [0] * (max_cost + 25)
	for (edge, i) in edges_cost.items():
		count = 1
		for num in edges_nodes[edge].values():
			count *= num
		while count > 0:
			if count & 1:
				res[i] += 1
			count >>= 1
			i += 1
	max_bit_set = 0
	for i in range(len(res)):
		if res[i] > 1:
			res[i + 1] += res[i] >> 1
			res[i] &= 1
		if res[i] == 1:
			max_bit_set = i
	res = res[:max_bit_set + 1]
	res.reverse()
	return ''.join([str(i) for i in res])
(n, m) = [int(i) for i in input().strip().split()]
roads = [dict() for _ in range(n)]
for _ in range(m):
	(i, j, dist) = list(map(int, input().rstrip().split()))
	(i, j) = (i - 1, j - 1)
	if not j in roads[i] or roads[i][j] > dist:
		roads[i][j] = dist
		roads[j][i] = dist
print(roadsInHackerland(n, roads))


(n, m) = map(int, input().strip().split())
parent = list(range(n))
rank = [0 for _ in range(n)]
size = [1 for _ in range(n)]
mst = [[] for _ in range(n)]

def find(a):
	if parent[a] == a:
		return a
	parent[a] = find(parent[a])
	return parent[a]

def unite(x, y, length):
	a = find(x)
	b = find(y)
	if a == b:
		return
	mst[x].append((y, length))
	mst[y].append((x, length))
	if rank[a] < rank[b]:
		parent[a] = b
		size[b] += size[a]
	else:
		parent[b] = a
		size[a] += size[b]
		if rank[a] == rank[b]:
			rank[a] += 1
edges = []
for i in range(m):
	(a, b, c) = map(int, input().strip().split())
	edges.append((c, a - 1, b - 1))
edges.sort()
for i in range(m):
	(c, a, b) = edges[i]
	unite(a, b, c)
	if size[find(a)] == n or size[find(b)] == n:
		break
root = 0
count = [0 for _ in range(2 * 10 ** 5)]

def dfs(node, parent):
	c = 1
	for (child, length) in mst[node]:
		if parent == child:
			continue
		c_ = dfs(child, node)
		count[length] = c_ * (n - c_)
		c += c_
	return c
dfs(root, -1)
s = 0
v = 1
for i in range(2 * 10 ** 5):
	s += v * count[i]
	v = v << 1
print(bin(s)[2:])


from heapq import *

def prim(edges):
	visited = [False] * len(edges)
	visited[0] = True
	n_visited = 1
	h = []
	for (child, weight) in edges[0]:
		heappush(h, (weight, 0, child))
	while h:
		if n_visited == len(edges):
			break
		(weight, parent, node) = heappop(h)
		if visited[node]:
			continue
		yield (parent, node, weight)
		visited[node] = True
		n_visited += 1
		for (child, weight) in edges[node]:
			if not visited[child]:
				heappush(h, (weight, node, child))

class Node:

	def __init__(self, data, parent_edge_weight=None):
		self.data = data
		self.parent_edge_weight = parent_edge_weight
		self.children = []
		self.weight = None

	def __str__(self):
		return '{} {} {}'.format(self.data, self.weight, [child.data for child in self.children])

	def division(self, root_weight):
		if self.parent_edge_weight is None:
			return (0, 0)
		return (self.weight * (root_weight - self.weight), self.parent_edge_weight)

def print_tree(root, level=0):
	return ' ' * level + str(root) + ''.join(('\n' + print_tree(child, level + 1) for child in root.children))

def tree(edges):
	root = Node(edges[0][0][0])
	stack = [(None, root)]
	stack_index = 0
	while stack_index < len(stack):
		(parent, node) = stack[stack_index]
		stack_index += 1
		for (child, weight) in edges[node.data]:
			if child == parent:
				continue
			new_node = Node(child, weight)
			node.children.append(new_node)
			stack.append((node.data, new_node))
	for (parent, node) in reversed(stack):
		node.weight = 1 + sum((child.weight for child in node.children))
	for (parent, node) in stack:
		yield node.division(root.weight)
(n, m) = (int(x) for x in input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c) = (int(x) for x in input().split())
	edges[a - 1].append((b - 1, c))
	edges[b - 1].append((a - 1, c))
new_edges = [[] for _ in range(n)]
for (a, b, c) in prim(edges):
	new_edges[a].append((b, c))
	new_edges[b].append((a, c))
edges = new_edges
total = 0
for (n, w) in tree(new_edges):
	total += n << w
print(bin(total)[2:])


list1 = list(range(10 ** 6))

def parents(v):
	if list1[v] != v:
		list1[v] = parents(list1[v])
	return list1[v]

def merge_edges(u, v):
	u = parents(u)
	v = parents(v)
	list1[u] = v
	return u != v
(n, m) = map(int, input().split())
roads = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	roads += [(c, b - 1, a - 1)]
roads.sort()
Graph = [[] for x in range(n)]
for (c, a, b) in roads:
	if merge_edges(a, b):
		Graph[a] += [(b, c)]
		Graph[b] += [(a, c)]
f = [0] * m

def dfs_graph(v, par=-1):
	sz = 1
	for (u, c) in Graph[v]:
		if u == par:
			continue
		y = dfs_graph(u, v)
		f[c] = y * (n - y)
		sz += y
	return sz
dfs_graph(0)
i = 0
for x in f[::-1]:
	i = i * 2
	i = i + x
print(bin(i)[2:])


import os
import sys
import heapq
from collections import defaultdict, deque

def mst(e, n):
	faction_arr = list(range(n + 1))
	edges = sorted([(e[k], k[0], k[1]) for k in e])

	def find_parent(node):
		root = node
		while faction_arr[root] != root:
			root = faction_arr[root]
		faction_arr[node] = root
		return faction_arr[node]
	i = 0
	mst_edges = {}
	while len(mst_edges) < n - 1:
		(w, s, d) = edges[i]
		if find_parent(s) != find_parent(d):
			faction_arr[find_parent(d)] = find_parent(s)
			mst_edges[s, d] = w
		i += 1
	return mst_edges

def get_edge_cnts(e):
	g = defaultdict(dict)
	for (s, d) in e:
		g[s][d] = -1
		g[d][s] = -1
	n = len(g)
	visited = set()
	for node in range(1, n + 1):
		if node not in visited:
			q = deque()
			q.append((0, node))
			while len(q) > 0:
				(p, cur) = q.pop()
				if len(g[cur]) == 1:
					for dest in g[cur]:
						g[cur][dest] = n - 1
						g[dest][cur] = 1
				else:
					unk = set()
					n_other_child = 0
					for dest in set(g[cur]) - {p}:
						if g[cur][dest] == -1:
							unk.add(dest)
						else:
							n_other_child += g[cur][dest]
					if len(unk) == 0:
						g[p][cur] = n_other_child + 1
						g[cur][p] = n - g[p][cur]
					else:
						q.append((p, cur))
						for d in unk:
							q.append((cur, d))
				visited.add(cur)
	return {(s, d): g[s][d] * g[d][s] for s in g for d in g[s] if s < d}
(n, m) = map(int, input().split())
edges = {}
for i in range(m):
	(s, d, c) = map(int, input().split())
	if s > d:
		(s, d) = (d, s)
	if (s, d) not in edges or c < edges[s, d]:
		edges[s, d] = c
edges = mst(edges, n)
edge_cnts = get_edge_cnts(edges)
tot_sum = 0
for (s, d) in edges:
	tot_sum += edge_cnts[s, d] << edges[s, d]
print(bin(tot_sum)[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


import os
import sys
from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from heapq import heappush, heappop
ra = lambda x: map(x, input().strip().split())

def prim(g):
	h = []
	res = [[[], 0] for _ in range(len(g))]
	s = [False for _ in range(len(g))]
	s[0] = True
	for (u, c) in g[0]:
		heappush(h, (c, u, 0))
	rs = 0
	while h:
		(c, v, u) = heappop(h)
		if s[v]:
			continue
		s[v] = True
		res[u][0].append((v, c))
		for (u, cc) in g[v]:
			if s[u]:
				continue
			heappush(h, (cc, u, v))
	return res

def dfs_calc(tree):
	rev = []
	st = [0]
	while st:
		ind = st.pop()
		rev.append(ind)
		for i in range(len(tree[ind][0])):
			(v, c) = tree[ind][0][i]
			st.append(v)
	for i in range(len(rev) - 1, -1, -1):
		ind = rev[i]
		for (v, _) in tree[ind][0]:
			tree[ind][1] += tree[v][1]
		tree[ind][1] += 1

def calc_cb(tree):
	st = [(0, 0)]
	d = dict()
	while st:
		(ind, cc) = st.pop()
		k = tree[ind][1] + cc
		for (v, c) in tree[ind][0]:
			kk = tree[v][1]
			d[c] = (k - kk) * kk
			st.append((v, k - kk))
	return d
(n, m) = ra(int)
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c) = ra(int)
	a -= 1
	b -= 1
	g[a].append((b, c))
	g[b].append((a, c))
mpt = prim(g)
dfs_calc(mpt)
counter = sorted(calc_cb(mpt).items())
result = []
carry = 0
ci = 0
for i in range(counter[-1][0] + 1):
	if counter[ci][0] == i:
		carry += counter[ci][1]
		ci += 1
	if carry & 1:
		result.append('1')
	else:
		result.append('0')
	carry >>= 1
while carry:
	if carry & 1:
		result.append('1')
	else:
		result.append('0')
	carry >>= 1
print(''.join(result[::-1]))


p = list(range(10 ** 5))
(n, m) = map(int, input().split())
e = []

def get(a):
	if p[a] != a:
		p[a] = get(p[a])
	return p[a]

def merge(a, b):
	a = get(a)
	b = get(b)
	p[a] = b
	return a != b

def dfs(v, p=-1):
	s = 1
	for (u, c) in G[v]:
		if u == p:
			continue
		y = dfs(u, v)
		f[c] = y * (n - y)
		s += y
	return s
for i in range(m):
	(a, b, c) = map(int, input().split())
	e += [(c, b - 1, a - 1)]
e.sort()
G = [[] for x in range(n)]
for (c, a, b) in e:
	if merge(a, b):
		G[a] += [(b, c)]
		G[b] += [(a, c)]
f = [0] * m
dfs(0)
ret = 0
for x in f[::-1]:
	ret *= 2
	ret += x
print(bin(ret)[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(x):
	while x != parent[parent[x]]:
		parent[x] = parent[parent[x]]
		x = parent[x]
	return x

def union(x, y):
	p1 = find(x)
	p2 = find(y)
	parent[p2] = p1

def connect(x, y):
	p1 = find(x)
	p2 = find(y)
	return p1 == p2

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			child = dfs(v, src)
			ans[c] += (n - child) * child
			total += child
	return total
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not connect(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


from collections import defaultdict
(n, m) = map(int, input().split())
edges = []
parent = [i for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))

def find(i):
	while i != parent[parent[i]]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i

def union(x, y):
	p_x = find(x)
	p_y = find(y)
	parent[p_y] = p_x

def is_connected(x, y):
	p_x = find(x)
	p_y = find(y)
	return p_x == p_y
tree = defaultdict(list)
edges.sort(key=lambda x: x[2])
for (a, b, c) in edges:
	if not is_connected(a, b):
		union(a, b)
		tree[a].append((b, c))
		tree[b].append((a, c))
ans = [0] * (2 * m)

def dfs(src, p=-1):
	total = 1
	for (v, c) in tree[src]:
		if v != p:
			children = dfs(v, src)
			ans[c] += (n - children) * children
			total += children
	return total
dfs(0)
res = 0
for i in range(len(ans)):
	res += ans[i] * (1 << i)
print(str(bin(res))[2:])


p = list(range(10 ** 5))

def dsu_get(v):
	if p[v] != v:
		p[v] = dsu_get(p[v])
	return p[v]

def dsu_merge(u, v):
	u = dsu_get(u)
	v = dsu_get(v)
	p[u] = v
	return u != v
(n, m) = map(int, input().split())
e = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	e += [(c, b - 1, a - 1)]
e.sort()
G = [[] for x in range(n)]
for (c, a, b) in e:
	if dsu_merge(a, b):
		G[a] += [(b, c)]
		G[b] += [(a, c)]
f = [0] * m

def dfs(v, par=-1):
	sz = 1
	for (u, c) in G[v]:
		if u == par:
			continue
		y = dfs(u, v)
		f[c] = y * (n - y)
		sz += y
	return sz
dfs(0)
ans = 0
for x in f[::-1]:
	ans *= 2
	ans += x
print(bin(ans)[2:])


import heapq
import time
start_time = time.time()
(n_nodes, n_edges) = map(int, input().split())
graph = {}
links_req = n_nodes - 1
links_made = 0
sorted_edges = []
heapq.heapify(sorted_edges)
links = {}
weights = {}
MST = []
MST_dict = {}
for _ in range(n_edges):
	(l_node_temp, r_node_temp, wt) = map(int, input().split())
	l_node = min(l_node_temp, r_node_temp)
	r_node = max(l_node_temp, r_node_temp)
	if (l_node, r_node) in graph:
		if wt < graph[l_node, r_node]:
			graph[l_node, r_node] = wt
		continue
	graph[l_node, r_node] = wt
for pair in graph:
	(l_node, r_node) = pair
	wt = graph[pair]
	heapq.heappush(sorted_edges, (wt, l_node, r_node))
universal_set = set(range(1, n_nodes + 1))
while links_made < links_req:
	trio = heapq.heappop(sorted_edges)
	(wt, l_node, r_node) = trio
	can_make_link = True
	if l_node not in universal_set and r_node not in universal_set:
		if MST_dict[l_node] == MST_dict[r_node]:
			can_make_link = False
	if can_make_link:
		if l_node not in links:
			links[l_node] = {r_node}
			weights[l_node] = {}
		else:
			links[l_node].add(r_node)
		if r_node not in links:
			links[r_node] = {l_node}
			weights[r_node] = {}
		else:
			links[r_node].add(l_node)
		weights[l_node][r_node] = wt
		weights[r_node][l_node] = wt
		links_made += 1
		new_pair = False
		if l_node in universal_set and r_node in universal_set:
			new_pair = True
			universal_set.remove(l_node)
			universal_set.remove(r_node)
		if new_pair:
			MST.append({l_node, r_node})
			MST_dict[l_node] = len(MST) - 1
			MST_dict[r_node] = len(MST) - 1
		elif l_node in universal_set:
			universal_set.remove(l_node)
			r_node_set = MST_dict[r_node]
			MST[r_node_set].add(l_node)
			MST_dict[l_node] = r_node_set
		elif r_node in universal_set:
			universal_set.remove(r_node)
			l_node_set = MST_dict[l_node]
			MST[l_node_set].add(r_node)
			MST_dict[r_node] = l_node_set
		else:
			l_node_set = MST_dict[l_node]
			r_node_set = MST_dict[r_node]
			len_LNS = len(MST[l_node_set])
			len_RNS = len(MST[r_node_set])
			bigger = l_node_set if len_LNS >= len_RNS else r_node_set
			smaller = l_node_set if len_LNS < len_RNS else r_node_set
			MST[bigger].update(MST[smaller])
			for element in MST[smaller]:
				MST_dict[element] = bigger
			MST[smaller] = set()
MST_time = time.time()
total = 0
root = 1
visit_order = [root]
heap_control = 1
visit_heap = [(heap_control, root)]
heapq.heapify(visit_heap)
seen = set()
total_children = [0] * (n_nodes + 1)
total_calls = [0] * (n_nodes + 1)
while visit_heap:
	(heap_control, current_node) = heapq.heappop(visit_heap)
	seen.add(current_node)
	for neighbour in links[current_node]:
		if neighbour in seen:
			continue
		visit_order.append(neighbour)
		heapq.heappush(visit_heap, (heap_control + 1, neighbour))
visit_order.reverse()
for current_node in visit_order:
	seen.remove(current_node)
	total_calls = (n_nodes - 1 - total_children[current_node]) * (1 + total_children[current_node])
	for neighbour in links[current_node]:
		if neighbour in seen:
			total_children[neighbour] += 1 + total_children[current_node]
			total += total_calls * (1 << weights[current_node][neighbour])
			break
print(str(bin(total))[2:])
end_time = time.time()