Japanese Student Championship 2019 Qualification - Card Collector

There are N cards placed on a grid with H rows and W columns of squares.

The i-th card has an integer A_i written on it, and it is placed on the square at the R_i-th row from the top and the C_i-th column from the left.

Multiple cards may be placed on the same square.

You will first pick up at most one card from each row.

Then, you will pick up at most one card from each column.

Find the maximum possible sum of the integers written on the picked cards.

Constraints

* All values are integers.
* 1 \leq N \leq 10^5
* 1 \leq H, W \leq 10^5
* 1 \leq A_i \leq 10^5
* 1 \leq R_i \leq H
* 1 \leq C_i \leq W

Input

Input is given from Standard Input in the following format:


N H W
R_1 C_1 A_1
R_2 C_2 A_2
\vdots
R_N C_N A_N


Output

Print the maximum possible sum of the integers written on the picked cards.

Examples

Input

6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4


Output

28


Input

13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537


Output

430590


Input

1 100000 100000
1 1 1


Output

1

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
(N, H, W) = map(int, readline().split())
RCA = [tuple((int(x) for x in line.split())) for line in readlines()]
RCA.sort(key=lambda x: -x[2])
RCA
root = list(range(H + W))
size = [0] * (H + W)
no_cycle = [True] * (H + W)

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

def merge(x, y):
	(x, y) = (find_root(x), find_root(y))
	(sx, sy) = (size[x], size[y])
	if sx < sy:
		(sx, sy) = (sy, sx)
		(x, y) = (y, x)
	root[y] = x
	no_cycle[x] = no_cycle[x] and no_cycle[y]
answer = 0
for (R, C, A) in RCA:
	(x, y) = (R - 1, H + C - 1)
	(rx, ry) = (find_root(x), find_root(y))
	if rx == ry:
		if not no_cycle[rx]:
			continue
		no_cycle[rx] = False
	else:
		if not no_cycle[rx] and (not no_cycle[ry]):
			continue
		merge(rx, ry)
	answer += A
print(answer)


class UnionFind:

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

	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:
			self.cycle[x] = True
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.cycle[x] |= self.cycle[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.cycle[y] |= self.cycle[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

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

	def isSafe(self, x, y):
		cx = self.cycle[self.find(x)]
		cy = self.cycle[self.find(y)]
		return not (self.isSame(x, y) and (cx or cy) or (cx and cy))
(n, h, w, *l) = map(int, open(0).read().split())
cards = sorted([(a, r - 1, c - 1) for (r, c, a) in zip(*[iter(l)] * 3)])[::-1]
uf = UnionFind(h + w)
ans = 0
for (a, r, c) in cards:
	c += h
	if uf.isSafe(r, c):
		uf.unite(r, c)
		ans += a
print(ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
import operator
(N, H, W) = map(int, readline().split())
m = map(int, read().split())
RCA = sorted(zip(m, m, m), key=operator.itemgetter(2), reverse=True)
root = list(range(H + W))
size = [0] * (H + W)
no_cycle = [True] * (H + W)

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

def merge(x, y):
	(x, y) = (find_root(x), find_root(y))
	(sx, sy) = (size[x], size[y])
	if sx < sy:
		(sx, sy) = (sy, sx)
		(x, y) = (y, x)
	root[y] = x
	no_cycle[x] = no_cycle[x] and no_cycle[y]
answer = 0
for (R, C, A) in RCA:
	(x, y) = (R - 1, H + C - 1)
	(rx, ry) = (find_root(x), find_root(y))
	if rx == ry:
		if not no_cycle[rx]:
			continue
		no_cycle[rx] = False
	else:
		if not no_cycle[rx] and (not no_cycle[ry]):
			continue
		merge(rx, ry)
	answer += A
print(answer)


class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.size = [1] * n
		self.rank = [0] * n
		self.edge = [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 is_saturated(self, x):
		x = self.find(x)
		return self.edge[x] == self.size[x]

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

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		self.edge[x] += 1
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.size[y] += self.size[x]
			self.edge[y] += self.edge[x]
		else:
			self.par[y] = x
			self.size[x] += self.size[y]
			self.edge[x] += self.edge[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
(n, h, w) = [int(item) for item in input().split()]
UF = UnionFind(h + w)
arc = []
for i in range(n):
	(r, c, a) = [int(item) for item in input().split()]
	r -= 1
	c -= 1
	c += h
	arc.append([a, r, c])
arc.sort(reverse=True)
ans = 0
for (a, r, c) in arc:
	if not UF.is_saturated(r) or not UF.is_saturated(c):
		UF.union(r, c)
		ans += a
print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 13

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

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

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class UnionFind:

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

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

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

	def get_size(self, x):
		return self.size[self.root(x)]

	def unite(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
			self.size[r1] += self.size[r2]
			self.cycle[r1] += self.cycle[r2]
			if d1 == d2:
				self.table[r1] -= 1
		else:
			self.table[r1] = r2
			self.size[r2] += self.size[r1]
			self.cycle[r2] += self.cycle[r1]
		self.group_num -= 1

	def get_cycle(self, x):
		return self.cycle[self.root(x)]

	def add_cycle(self, x):
		self.cycle[self.root(x)] += 1
		return
(n, h, w) = LI()
uf = UnionFind(h + w)
ans = 0
rca = sorted(LIR(n), key=lambda x: x[2], reverse=True)
for (r, c, a) in rca:
	r -= 1
	c -= 1
	if uf.is_same(r, h + c):
		if uf.get_cycle(r):
			continue
		else:
			uf.add_cycle(r)
			ans += a
	elif uf.get_cycle(uf.root(r)) and uf.get_cycle(uf.root(h + c)):
		continue
	else:
		uf.unite(r, h + c)
		ans += a
print(ans)


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

def main():

	def get_group(k):
		g = pd[k]
		if g < 0:
			return k
		gg = get_group(g)
		pd[k] = gg
		return gg

	def merge(j, k):
		g1 = get_group(j)
		g2 = get_group(k)
		if g1 != g2:
			d1 = -pd[g1]
			d2 = -pd[g2]
			if d2 > d1:
				(g1, g2) = (g2, g1)
			pd[g2] = g1
			if d1 == d2:
				pd[g1] -= 1
	hp = []
	(n, h, w) = map(int, input().split())
	pd = [-1] * (h + w + 2)
	pd[0] = -(h + w + 2)
	for _ in range(n):
		(r, c, a) = map(int, input().split())
		heappush(hp, [-a, r, h + c])
	cnt = h + w
	ans = 0
	while cnt and hp:
		(a, r, c) = heappop(hp)
		gr = get_group(r)
		gc = get_group(c)
		if gr + gc == 0:
			continue
		if gr == gc:
			merge(gr, 0)
		else:
			merge(gr, gc)
		ans -= a
		cnt -= 1
	print(ans)
main()


import sys
sys.setrecursionlimit(10 ** 5)

class UnionFind:

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

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

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			new_root = r1
		else:
			d1 = self.table[r1]
			d2 = self.table[r2]
			if d1 <= d2:
				self.table[r2] = r1
				self.table[r1] += d2
				self.taken[r1] += self.taken[r2]
				new_root = r1
			else:
				self.table[r1] = r2
				self.table[r2] += d1
				self.taken[r2] += self.taken[r1]
				new_root = r2
		cells = -self.table[new_root]
		taken = self.taken[new_root]
		if cells > taken:
			self.taken[new_root] += 1
			return True
		return False
(n, h, w) = map(int, input().split())
hw = h + w
cards = []
for line in sys.stdin:
	(r, c, a) = map(int, line.split())
	cards.append((a, r - 1, h + c - 1))
cards.sort(reverse=True)
uft = UnionFind(hw)
ans = 0
for (a, r, c) in cards:
	if uft.union(r, c):
		ans += a
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, h, w) = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
	(r, c, a) = list(map(int, input().split()))
	r -= 1
	c -= 1
	c += h
	ns[r].append((a, c))
	ns[c].append((a, r))

class UnionFindTree:

	def __init__(self, n):
		self.n = n
		self.parent = list(range(n))
		self.size = [1] * n
		self.es = [0] * n

	def root(self, i):
		inter = set()
		while self.parent[i] != i:
			inter.add(i)
			i = self.parent[i]
		r = i
		for i in inter:
			self.parent[i] = r
		return r

	def connect(self, i, j):
		ri = self.root(i)
		rj = self.root(j)
		if ri == rj:
			self.es[ri] += 1
			return
		if self.size[ri] < self.size[rj]:
			self.parent[ri] = rj
			self.size[rj] += self.size[ri]
			self.es[rj] += self.es[ri] + 1
		else:
			self.parent[rj] = ri
			self.size[ri] += self.size[rj]
			self.es[ri] += self.es[rj] + 1

def selectEdge(ns):
	from heapq import heappop as hpp, heappush as hp
	q = []
	for u in ns.keys():
		for (a, v) in ns[u]:
			if u < v:
				hp(q, (-a, (u, v)))
	uf = UnionFindTree(h + w)
	ans = 0
	while q:
		(a, (u, v)) = hpp(q)
		a *= -1
		ru = uf.root(u)
		rv = uf.root(v)
		if ru == rv and uf.es[ru] < uf.size[ru]:
			uf.connect(u, v)
			ans += a
		elif ru != rv and uf.es[ru] + uf.es[rv] + 1 <= uf.size[ru] + uf.size[rv]:
			uf.connect(u, v)
			ans += a
	return (ans, uf)
(ans, uf) = selectEdge(ns)
print(ans)


import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
(N, H, W) = map(int, input().split())
RCA = []

class UF(object):

	def __init__(self, n):
		self.parent = [i for i in range(n)]

	def root(self, v):
		if v == self.parent[v]:
			return v
		else:
			self.parent[v] = self.root(self.parent[v])
			return self.parent[v]

	def unite(self, u, v):
		(u, v) = (self.root(u), self.root(v))
		if u == v:
			return
		self.parent[u] = v
for _ in range(N):
	(r, c, a) = map(int, input().split())
	(r, c) = (r - 1, c - 1)
	RCA.append((a, r, c))
RCA.sort(reverse=True)
RCA = deque(RCA)
uf = UF(H + W + 1)
(cnt, ans) = (0, 0)
while RCA and cnt < H + W:
	(a, r, c) = RCA.popleft()
	c += H
	if uf.root(r) == uf.root(c):
		if uf.root(r) == uf.root(H + W):
			continue
		uf.unite(r, H + W)
	ans += a
	cnt += 1
	uf.unite(r, c)
print(ans)


def wantp(x):
	wpq = []
	while p[x] != x:
		wpq.append(x)
		x = p[x]
	for i in wpq:
		p[i] = x
	return x
(N, H, W) = map(int, input().split())
ans = 0
ARC = []
for i in range(N):
	(r, c, a) = map(int, input().split())
	ARC.append([a, r - 1, c - 1])
ARC.sort()
ARC.reverse()
huse = [-1] * H
wuse = [-1] * W
p = [i for i in range(N)]
lnum = [0] * N
rank = [1] * N
for i in range(N):
	na = ARC[i][0]
	nr = ARC[i][1]
	nc = ARC[i][2]
	nowp = wantp(i)
	if huse[nr] == -1:
		lnum[nowp] += 1
		huse[nr] = nowp
	else:
		hp = wantp(huse[nr])
		if hp != nowp:
			if rank[hp] > rank[nowp]:
				p[nowp] = hp
				lnum[hp] += lnum[nowp]
			elif rank[hp] < rank[nowp]:
				p[hp] = nowp
				lnum[nowp] += lnum[hp]
			else:
				p[hp] = nowp
				lnum[nowp] += lnum[hp]
				rank[nowp] += 1
	nowp = wantp(i)
	if wuse[nc] == -1:
		lnum[nowp] += 1
		wuse[nc] = nowp
	else:
		wp = wantp(wuse[nc])
		if wp != nowp:
			if rank[wp] > rank[nowp]:
				p[nowp] = wp
				lnum[wp] += lnum[nowp]
			elif rank[wp] < rank[nowp]:
				p[wp] = nowp
				lnum[nowp] += lnum[wp]
			else:
				p[wp] = nowp
				lnum[nowp] += lnum[wp]
				rank[nowp] += 1
	nowp = wantp(i)
	if lnum[nowp] > 0:
		ans += na
		lnum[nowp] -= 1
print(ans)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

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

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

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	(m, d) = LI()
	ans = 0
	for i in range(1, m + 1):
		for j in range(1, d + 1):
			d1 = j % 10
			d2 = j // 10
			if d1 >= 2 and d2 >= 2 and (d1 * d2 == i):
				ans += 1
	print(ans)
	return

def B():

	def add(i):
		while i <= m:
			bit[i] += 1
			i += i & -i

	def sum(i):
		res = 0
		while i > 0:
			res += bit[i]
			i -= i & -i
		return res
	(n, k) = LI()
	m = 2000
	a = LI()
	bit = [0] * (m + 1)
	ans = 0
	for i in range(n):
		ans += (i - sum(a[i])) * k
		add(a[i])
	inv = pow(2, mod - 2, mod)
	for i in range(n):
		ans += sum(a[i] - 1) * k * (k - 1) * inv % mod
	print(ans % mod)
	return

def C():
	n = I()
	s = S()
	if 'W' in (s[0], s[-1]):
		print(0)
		return
	d = [0]
	for i in range(1, 2 * n):
		if s[i] == s[i - 1]:
			d.append(1 - d[-1])
		else:
			d.append(d[-1])
	if sum(d) != n:
		print(0)
		return
	ans = 1
	s = 0
	for i in d:
		if not i:
			s += 1
		else:
			ans *= s
			s -= 1
			ans %= mod
	for i in range(1, n + 1):
		ans *= i
		ans %= mod
	print(ans)
	return

def D():
	n = I()
	m = n.bit_length()
	v = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(n):
			k = i ^ j
			for l in range(m):
				if k & 1 << l:
					v[i][j] = l + 1
					break
	for i in range(n - 1):
		print(*v[i][i + 1:])
	return

def E():

	def root(x):
		if par[x] == x:
			return x
		par[x] = root(par[x])
		return par[x]

	def unite(x, y):
		x = root(x)
		y = root(y)
		if rank[x] < rank[y]:
			par[x] = y
			s[y] += s[x]
			e[y] += e[x] + 1
		else:
			par[y] = x
			s[x] += s[y]
			e[x] += e[y] + 1
			if rank[x] == rank[y]:
				rank[x] += 1
	(n, h, w) = LI()
	v = []
	m = h + w
	for i in range(n):
		(r, c, a) = LI()
		r -= 1
		c += h - 1
		v.append((a, r, c))
	v.sort(key=lambda x: -x[0])
	par = [i for i in range(m)]
	rank = [0] * m
	s = [1] * m
	e = [0] * m
	ans = 0
	for (a, x, y) in v:
		(rx, ry) = (root(x), root(y))
		if rx == ry:
			if e[rx] + 1 <= s[rx]:
				ans += a
				e[rx] += 1
		elif e[rx] + e[ry] + 1 <= s[rx] + s[ry]:
			ans += a
			unite(x, y)
	print(ans)
	return

def F():
	return
E()


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.cycle = [0] * n

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

	def merge(self, x, y):
		(x, y) = (self.root(x), self.root(y))
		if x == y:
			return False
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.size[x] += self.size[y]
		self.parent[y] = x
		self.cycle[x] = self.cycle[x] + self.cycle[y]
		return True

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

	def getsize(self, x):
		return self.size[self.root(x)]

	def getcycle(self, x):
		return self.cycle[self.root(x)]

	def addcycle(self, x):
		self.cycle[self.root(x)] += 1
		return
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(n, h, w) = [int(i) for i in readline().split()]
uf = UnionFind(h + w)
rca = [[int(i) - 1 for i in readline().split()] for i in range(n)]
from operator import itemgetter
rca.sort(key=itemgetter(2), reverse=True)
ans = 0
for (r, c, a) in rca:
	c += h
	a += 1
	if uf.issame(r, c):
		if uf.getcycle(r):
			continue
		ans += a
		uf.addcycle(r)
	else:
		if uf.getcycle(r) + uf.getcycle(c) >= 2:
			continue
		uf.merge(r, c)
		ans += a
print(ans)


class UnionFindNode:

	def __init__(self, group_id, parent=None, value=None):
		self.group_id_ = group_id
		self.parent_ = parent
		self.value = value
		self.rank_ = 1
		self.member_num_ = 1
		self.enum = 0

	def is_root(self):
		return not self.parent_

	def root(self):
		parent = self
		while not parent.is_root():
			parent = parent.parent_
			self.parent_ = parent
		return parent

	def find(self):
		root = self.root()
		return root.group_id_

	def rank(self):
		root = self.root()
		return root.rank_

	def unite(self, unite_node):
		root = self.root()
		unite_root = unite_node.root()
		if not self.check(unite_node):
			return False
		if root.group_id_ != unite_root.group_id_:
			if root.rank() > unite_root.rank():
				unite_root.parent_ = root
				root.rank_ = max(root.rank_, unite_root.rank_ + 1)
				root.member_num_ = root.member_num_ + unite_root.member_num_
				root.enum = root.enum + unite_root.enum + 1
			else:
				root.parent_ = unite_root
				unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
				unite_root.member_num_ = root.member_num_ + unite_root.member_num_
				unite_root.enum = root.enum + unite_root.enum + 1
		else:
			root.enum += 1
		return True

	def check(self, unite_node):
		root = self.root()
		unite_root = unite_node.root()
		if root.group_id_ == unite_root.group_id_:
			if root.enum < root.member_num_:
				return True
		elif root.member_num_ + unite_root.member_num_ > root.enum + unite_root.enum:
			return True
		return False
(N, H, W) = [int(i) for i in input().strip().split(' ')]
node_list = [UnionFindNode(i) for i in range(H + W)]
import sys
es = []
for line in sys.stdin:
	es.append(tuple((int(i) for i in line.strip().split(' '))))
es = sorted(es, key=lambda x: x[2])
r = 0
for e in es[::-1]:
	if node_list[e[0] - 1].unite(node_list[e[1] + H - 1]):
		r += e[2]
print(r)


class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self._edge = [0] * N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			self._edge[gx] += 1
			return
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
			self._edge[gy] += self._edge[gx] + 1
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]
			self._edge[gx] += self._edge[gy] + 1

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def calc_group_num(self):
		N = len(self._parent)
		ans = 0
		for i in range(N):
			if self.find_root(i) == i:
				ans += 1
		return ans

	def check(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return self._size[gx] >= self._edge[gx] + 1
		else:
			nv = self._size[gx] + self._size[gy]
			ne = self._edge[gx] + self._edge[gy] + 1
			return nv >= ne
import sys
input = sys.stdin.readline
(N, H, W) = map(int, input().split())
card = []
for i in range(N):
	(r, c, a) = map(int, input().split())
	card.append((a, r - 1, c - 1))
card.sort()
uf = UnionFindVerSize(H + W)
ans = 0
while card:
	(val, r, c) = card.pop()
	if uf.check(r, H + c):
		uf.unite(r, H + c)
		ans += val
print(ans)


import sys
readline = sys.stdin.readline

class UF:

	def __init__(self, num):
		self.par = [-1] * num
		self.comp = [False] * num

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			stack = []
			while self.par[x] >= 0:
				stack.append(x)
				x = self.par[x]
			for xi in stack:
				self.par[xi] = x
			return x

	def union(self, x, y):
		rx = self.find(x)
		ry = self.find(y)
		if rx != ry:
			if self.comp[rx] and self.comp[ry]:
				return False
			if self.par[rx] > self.par[ry]:
				(rx, ry) = (ry, rx)
			self.comp[rx] |= self.comp[ry]
			self.par[rx] += self.par[ry]
			self.par[ry] = rx
			return True
		elif not self.comp[rx]:
			self.comp[rx] = True
			return True
		return False
(N, H, W) = map(int, readline().split())
geta = 10 ** 5
Edge = []
for _ in range(N):
	(h, w, a) = map(int, readline().split())
	h -= 1
	w -= 1
	Edge.append((a, h, geta + w))
Edge.sort(reverse=True)
T = UF(2 * geta)
ans = 0
for (cost, a, b) in Edge:
	if T.union(a, b):
		ans += cost
print(ans)