The integers shop sells $n$ segments. The $i$-th of them contains all integers from $l_i$ to $r_i$ and costs $c_i$ coins.

Tomorrow Vasya will go to this shop and will buy some segments there. He will get all integers that appear in at least one of bought segments. The total cost of the purchase is the sum of costs of all segments in it.

After shopping, Vasya will get some more integers as a gift. He will get integer $x$ as a gift if and only if all of the following conditions are satisfied:

Vasya hasn't bought $x$.

Vasya has bought integer $l$ that is less than $x$.

Vasya has bought integer $r$ that is greater than $x$.

Vasya can get integer $x$ as a gift only once so he won't have the same integers after receiving a gift.

For example, if Vasya buys segment $[2, 4]$ for $20$ coins and segment $[7, 8]$ for $22$ coins, he spends $42$ coins and receives integers $2, 3, 4, 7, 8$ from these segments. He also gets integers $5$ and $6$ as a gift.

Due to the technical issues only the first $s$ segments (that is, segments $[l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]$) will be available tomorrow in the shop.

Vasya wants to get (to buy or to get as a gift) as many integers as possible. If he can do this in differents ways, he selects the cheapest of them.

For each $s$ from $1$ to $n$, find how many coins will Vasya spend if only the first $s$ segments will be available.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \leq n \leq 10^5$) — the number of segments in the shop.

Each of next $n$ lines contains three integers $l_i$, $r_i$, $c_i$ ($1 \leq l_i \leq r_i \leq 10^9, 1 \leq c_i \leq 10^9$) — the ends of the $i$-th segments and its cost.

It is guaranteed that the total sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case output $n$ integers: the $s$-th ($1 \leq s \leq n$) of them should be the number of coins Vasia will spend in the shop if only the first $s$ segments will be available.


-----Examples-----

Input
3
2
2 4 20
7 8 22
2
5 11 42
5 11 42
6
1 4 4
5 8 9
7 8 7
2 10 252
1 11 271
1 10 1
Output
20
42
42
42
4
13
11
256
271
271


-----Note-----

In the first test case if $s = 1$ then Vasya can buy only the segment $[2, 4]$ for $20$ coins and get $3$ integers.

The way to get $7$ integers for $42$ coins in case $s = 2$ is described in the statement.

In the second test case note, that there can be the same segments in the shop.

Source: codeforces | Difficulty: MEDIUM
Tags: Data structures

Implementation

Greedy algorithms


Solutions:
from sys import stdin

def solve():
	for _ in range(int(stdin.readline().rstrip())):
		res = []
		(minL, maxR) = (10 ** 10, 0)
		(costL, costR) = (10 ** 10, 10 ** 10)
		(max_len, cost_len) = (0, 0)
		for _ in range(int(stdin.readline().rstrip())):
			(l, r, c) = map(int, stdin.readline().rstrip().split())
			if l < minL:
				minL = l
				costL = c
			elif l == minL:
				costL = min(costL, c)
			if r > maxR:
				maxR = r
				costR = c
			elif r == maxR:
				costR = min(costR, c)
			if max_len < r - l + 1:
				max_len = r - l + 1
				cost_len = c
			elif max_len == r - l + 1:
				cost_len = min(cost_len, c)
			if max_len == maxR - minL + 1:
				ans = min(costR + costL, cost_len)
			else:
				ans = costR + costL
			res.append(ans)
		print('\n'.join(map(str, res)))
solve()


import sys
ints = map(int, sys.stdin.read().split())
t = next(ints)
for _ in range(t):
	n = next(ints)
	left = None
	right = None
	cost_left = None
	cost_right = None
	covers = False
	cover_cost = 99999999999
	out = []
	for k in range(n):
		(a, b, c) = (next(ints), next(ints), next(ints))
		if left is None or a < left:
			left = a
			cost_left = c
			covers = False
			cover_cost = 99999999999
		elif left == a and c < cost_left:
			cost_left = c
		if right is None or b > right:
			right = b
			cost_right = c
			covers = False
			cover_cost = 99999999999
		elif right == b and c < cost_right:
			cost_right = c
		if left == a and right == b:
			covers = True
			cover_cost = min(cover_cost, c)
		if covers:
			out.append(str(min(cost_left + cost_right, cover_cost)))
		else:
			out.append(str(cost_left + cost_right))
	print('\n'.join(out))


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	d = dict()
	bl = (11 ** 9, -1)
	br = (0, -1)
	bad = 11 ** 9
	ans = [None] * n
	for i in range(n):
		(l, r, c) = map(int, inp().split())
		bl = min(bl, (l, c))
		br = max(br, (r, -c))
		d[l, r] = min(d.get((l, r), bad), c)
		ans[i] = min(bl[1] - br[1], d.get((bl[0], br[0]), bad))
	print('\n'.join(map(str, ans)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import math
for _ in range(int(input())):
	n = int(input())
	INF = pow(10, 10)
	best_left = INF
	best_right = -INF
	l_cost = INF
	r_cost = INF
	t_cost = INF
	result = []
	for i in range(n):
		(left, right, cost) = map(int, input().split())
		if left < best_left:
			l_cost = INF
			t_cost = INF
			best_left = left
		if right > best_right:
			r_cost = INF
			t_cost = INF
			best_right = right
		if left == best_left:
			l_cost = min(l_cost, cost)
		if right == best_right:
			r_cost = min(r_cost, cost)
		if left == best_left and right == best_right:
			t_cost = min(t_cost, cost)
		cost = min(l_cost + r_cost, t_cost)
		result.append(str(cost))
	print('\n'.join(result))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	mi = 10 ** 10
	ma = -1
	ans = sys.maxsize
	tmp = sys.maxsize
	for i in range(n):
		(l, r, c) = map(int, input().split())
		if mi > l:
			tmp = sys.maxsize
			mi = l
			mincost = c
		elif mi == l and mincost > c:
			mincost = c
		if ma < r:
			tmp = sys.maxsize
			ma = r
			maxcost = c
		elif ma == r and maxcost > c:
			maxcost = c
		if mi == l and ma == r:
			tmp = min(tmp, c)
		print(min(mincost + maxcost, tmp))


import sys
input = sys.stdin.readline
MAX = sys.maxsize

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

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

def solve(segments):
	(first, last) = (MAX, -1)
	(first_cost, last_cost) = (MAX, MAX)
	tmp = MAX
	for s in segments:
		((l, r), c) = s
		if first > l:
			tmp = MAX
			first = l
			first_cost = c
		elif first == l and first_cost > c:
			first_cost = c
		if last < r:
			tmp = MAX
			last = r
			last_cost = c
		elif last == r and last_cost > c:
			last_cost = c
		if first == l and last == r:
			tmp = min(tmp, c)
		print(min(first_cost + last_cost, tmp))
for _ in range(inp()):
	s = list()
	for _ in range(inp()):
		(l, r, c) = read_int_list()
		s.append(((l, r), c))
	solve(s)


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
import sys
input = sys.stdin.readline
import bisect

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

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

def fun():
	n = int(input())
	d = {}
	(ml, mr) = (10 ** 9 + 1, 0)
	(c1, c2) = (0, 0)
	for i in range(n):
		(l, r, c) = map(int, input().split())
		if l < ml:
			ml = l
			c1 = c
		elif l == ml:
			c1 = min(c1, c)
		if r > mr:
			mr = r
			c2 = c
		elif r == mr:
			c2 = min(c2, c)
		if (l, r) in d:
			d[l, r] = min(d[l, r], c)
		else:
			d[l, r] = c
		if (ml, mr) in d:
			print(min(d[ml, mr], c1 + c2))
		else:
			print(c1 + c2)
t = int(input())
for _ in range(t):
	fun()


from sys import *
input = stdin.readline
a = int(input())
for x in range(a):
	b = int(input())
	lmin = 99999999999
	rmax = 0
	lval = 99999999999
	rval = 99999999999
	maxsize = 0
	ans = 0
	for y in range(b):
		(c, d, e) = map(int, input().split())
		if d - c + 1 > maxsize or (d - c + 1 == maxsize and e < ans):
			maxsize = d - c + 1
			ans = e
		if c < lmin or (c == lmin and e < lval):
			lval = e
			lmin = c
		if d > rmax or (d == rmax and e < rval):
			rval = e
			rmax = d
		if maxsize == rmax - lmin + 1:
			print(min(ans, lval + rval))
		else:
			print(lval + rval)


import sys, heapq

def print(s):
	sys.stdout.write('{}\n'.format(s))
out = []
for t in range(int(input())):
	n = int(input())
	lo = 1000000001
	hi = 0
	mins = []
	maxs = []
	completes = []
	for s in range(n):
		(l, r, c) = map(int, input().split())
		if l == lo:
			heapq.heappush(mins, (c, l, r))
		elif l < lo:
			lo = l
			mins = []
			heapq.heappush(mins, (c, l, r))
			completes = []
		if r == hi:
			heapq.heappush(maxs, (c, l, r))
			if l == lo:
				heapq.heappush(completes, (c, l, r))
		elif r > hi:
			hi = r
			maxs = []
			completes = []
			heapq.heappush(maxs, (c, l, r))
			if l == lo:
				heapq.heappush(completes, (c, l, r))
		cheapestTwo = mins[0][0] + maxs[0][0]
		if len(completes) > 0:
			cheapestComplete = completes[0][0]
			out.append(min(cheapestComplete, cheapestTwo))
		else:
			out.append(cheapestTwo)
print('\n'.join(map(str, out)))


import sys
import typing
from typing import Callable, Dict, List, Set, Tuple
sys.setrecursionlimit(10 ** 6)
Vec = List[int]
VecVec = List[Vec]
sinput: Callable[..., str] = sys.stdin.readline
MOD: int = 998244353
INF: float = float('Inf')
IINF: int = sys.maxsize // 2

def main() -> None:
	n = int(sinput())
	lrc = [tuple(map(int, sinput().split())) for _ in range(n)]
	width = []
	cost = []
	max_w = 0
	min_c = IINF
	for (l, r, c) in lrc:
		if r - l + 1 > max_w:
			max_w = r - l + 1
			min_c = c
		elif r - l + 1 == max_w:
			min_c = min(min_c, c)
		width.append(max_w)
		cost.append(min_c)
	left = IINF
	left_cost = 0
	right = -IINF
	right_cost = 0
	for (i, (l, r, c)) in enumerate(lrc):
		if l < left:
			left = l
			left_cost = c
		elif l == left:
			left_cost = min(left_cost, c)
		if r > right:
			right = r
			right_cost = c
		elif r == right:
			right_cost = min(right_cost, c)
		if right - left + 1 > width[i]:
			cost[i] = left_cost + right_cost
		elif right - left + 1 == width[i]:
			cost[i] = min(cost[i], left_cost + right_cost)
	print(*cost, sep='\n')
t = int(sinput())
for _ in range(t):
	main()


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	minL = float('inf')
	maxR = float('-inf')
	costLR = float('inf')
	costL = None
	costR = None
	N = int(input())
	for x in range(N):
		(l, r, c) = map(int, input().split())
		if l < minL:
			costLR = float('inf')
			minL = l
			costL = c
		elif l == minL:
			costL = min(costL, c)
		if r > maxR:
			costLR = float('inf')
			maxR = r
			costR = c
		elif r == maxR:
			costR = min(costR, c)
		ans = costL + costR
		if l == minL and r == maxR:
			costLR = min(costLR, c)
		ans = min(ans, costLR)
		print(ans)


import sys
input = sys.stdin.readline
inf = 11000000000.0
for _ in range(int(input())):
	max_size = 0
	max_size_cost = 0
	(leftmost, rightmost) = (inf, 0)
	(l_cost, r_cost) = (0, 0)
	for i in range(int(input())):
		(l, r, cost) = map(int, input().split())
		if r - l + 1 > max_size or (r - l + 1 == max_size and max_size_cost > cost):
			max_size_cost = cost
			max_size = r - l + 1
		if l < leftmost or (l == leftmost and cost < l_cost):
			l_cost = cost
			leftmost = l
		if r > rightmost or (r == rightmost and cost < r_cost):
			r_cost = cost
			rightmost = r
		print([r_cost + l_cost, min(max_size_cost, r_cost + l_cost)][rightmost - leftmost + 1 == max_size])


out = []
t = int(input())
for i in range(t):
	n = int(input())
	left = float('inf')
	right = maxsize = maxsizecost = -float('inf')
	for j in range(n):
		(l, r, c) = map(int, input().split())
		if r - l + 1 > maxsize or (r - l + 1 == maxsize and c < maxsizecost):
			maxsize = r - l + 1
			maxsizecost = c
		if l < left or (l == left and c < lcost):
			lcost = c
			left = l
		if r > right or (r == right and c < rcost):
			rcost = c
			right = r
		if right - left + 1 == maxsize:
			out.append(min(maxsizecost, lcost + rcost))
		else:
			out.append(lcost + rcost)
print(*out, sep='\n')


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(input())
for rtt in range(t):
	n = int(input())
	a1 = 0
	a2 = 0
	b1 = 10 ** 9 + 1
	b2 = 0
	c1 = 0
	c2 = 0
	for r in range(n):
		(a, b, c) = get_ints()
		if a1 < b - a + 1 or (a1 == b - a + 1 and a2 > c):
			a1 = b - a + 1
			a2 = c
		if b1 > a or (b1 == a and b2 > c):
			b1 = a
			b2 = c
		if c1 < b or (c1 == b and c2 > c):
			c1 = b
			c2 = c
		if a1 > c1 - b1 + 1:
			sys.stdout.write(str(a2) + '\n')
		elif a1 == c1 - b1 + 1:
			sys.stdout.write(str(min(a2, b2 + c2)) + '\n')
		else:
			sys.stdout.write(str(b2 + c2) + '\n')


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')
A = 10 ** 9 + 1
for i in range(int(input())):
	n = int(input())
	(min_l, max_r) = (A, 0)
	(min_cost_min_l, min_cost_max_r) = (A, A)
	(max_length, min_cost_max_length) = (0, A)
	for j in range(n):
		(l, r, c) = map(int, input().split())
		if l == min_l:
			min_cost_min_l = min(min_cost_min_l, c)
		if l < min_l:
			min_l = l
			min_cost_min_l = c
		if r == max_r:
			min_cost_max_r = min(min_cost_max_r, c)
		if r > max_r:
			max_r = r
			min_cost_max_r = c
		if r - l + 1 == max_length:
			min_cost_max_length = min(min_cost_max_length, c)
		if r - l + 1 > max_length:
			max_length = r - l + 1
			min_cost_max_length = c
		if max_r - min_l + 1 == max_length:
			print(min(min_cost_max_length, min_cost_min_l + min_cost_max_r))
		else:
			print(min_cost_min_l + min_cost_max_r)


import sys
input = sys.stdin.readline
for test in range(int(input())):
	n = int(input())
	lm = 2 ** 69
	rm = -1
	res = 2 ** 69
	for _ in range(n):
		(l, r, c) = list(map(int, input().split()))
		if lm > l:
			lm = l
			mcl = c
			res = 2 ** 69
		elif lm == l and c < mcl:
			mcl = c
		if r > rm:
			rm = r
			mcr = c
			res = 2 ** 69
		elif r == rm and c < mcr:
			mcr = c
		if r == rm and l == lm:
			res = min(res, c)
		res = min(res, mcr + mcl)
		print(res)


I = open(0).readline
for _ in [0] * int(I()):
	x = y = z = 1e+62
	for _ in [0] * int(I()):
		(l, r, c) = map(int, I().split())
		x = min(x, l << 31 | c)
		y = min(y, -r << 31 | c)
		z = min(z, l - r << 31 | c)
		print(min(x + y, z) & 2 ** 31 - 1)


p = open(0).readline
for i in [0] * int(p()):
	x = y = z = 5e+18
	for f in [0] * int(p()):
		(l, r, c) = map(int, p().split())
		x = min(x, l << 31 | c)
		y = min(y, -r << 31 | c)
		print(min(x + y, (z := min(z, l - r << 31 | c))) & 2 ** 31 - 1)


I = open(0).readline
for _ in [0] * int(I()):
	x = y = z = 5e+18
	for _ in [0] * int(I()):
		(l, r, c) = map(int, I().split())
		x = min(x, l << 31 | c)
		y = min(y, -r << 31 | c)
		z = min(z, l - r << 31 | c)
		print(min(x + y, z) & 2 ** 31 - 1)


import sys

def sol(bestleft, besright, bestboth, l, r, c):
	if r - l > bestboth[1] - bestboth[0] or (r - l == bestboth[1] - bestboth[0] and c < bestboth[2]):
		bestboth = (l, r, c)
	if l < bestleft[0] or (l == bestleft[0] and c < bestleft[2]):
		bestleft = (l, r, c)
	if r > besright[1] or (r == besright[1] and c < besright[2]):
		besright = (l, r, c)
	if bestboth[1] - bestboth[0] == besright[1] - bestleft[0]:
		return (bestleft, besright, bestboth, min(bestboth[2], bestleft[2] + besright[2]))
	else:
		return (bestleft, besright, bestboth, bestleft[2] + besright[2])
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	bestleft = (float('inf'), float('-inf'), float('inf'))
	besright = (float('inf'), float('-inf'), float('inf'))
	bestboth = (float('inf'), float('-inf'), float('inf'))
	ans = float('inf')
	for _ in range(n):
		(l, r, c) = map(int, sys.stdin.readline().strip().split())
		(bestleft, besright, bestboth, ans) = sol(bestleft, besright, bestboth, l, r, c)
		print(ans)


p = open(0).readline
for i in [0] * int(p()):
	x = y = z = 5e+18
	for f in [0] * int(p()):
		(l, r, c) = map(int, p().split())
		x = min(x, l << 31 | c)
		y = min(y, -r << 31 | c)
		print(min(x + y, (z := min(z, l - r << 31 | c))) & 2 ** 31 - 1)
num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()


I = open(0).readline
for _ in [0] * int(I()):
	x = (2000000000.0, 2000000000.0)
	y = z = (0, 2000000000.0)
	for _ in [0] * int(I()):
		(l, r, c) = map(int, I().split())
		x = (d, e) = min(x, (l, c))
		y = (f, g) = min(y, (-r, c))
		z = min(z, (l - r, c))
		print(min((d + f, e + g), z)[1])


for _ in range(int(input())):
	n = int(input())
	si = [list(map(int, input().split())) for i in range(n)]
	lowest_number = si[0][0]
	highest_number = si[0][1]
	difference = highest_number - lowest_number
	lowest_cost = si[0][2]
	highest_cost = si[0][2]
	difference_cost = si[0][2]
	print(si[0][2])
	for i in si[1:]:
		(si0, si1, si2) = i
		if si0 < lowest_number or (si0 == lowest_number and si2 < lowest_cost):
			lowest_number = si0
			lowest_cost = si2
		if si1 > highest_number or (si1 == highest_number and si2 < highest_cost):
			highest_number = si1
			highest_cost = si2
		if si1 - si0 > difference or (si1 - si0 == difference and si2 < difference_cost):
			difference = si1 - si0
			difference_cost = si2
		if difference == highest_number - lowest_number:
			print(min(difference_cost, lowest_cost + highest_cost))
		else:
			print(lowest_cost + highest_cost)


import sys
INT_MAX = sys.maxsize
inp = sys.stdin.readline
for _ in range(int(inp())):
	n = int(inp())
	d = {}
	ml = (INT_MAX, INT_MAX)
	mr = (0, -1)
	for i in range(n):
		(l, r, c) = map(int, inp().split())
		ml = min(ml, (l, c))
		mr = max(mr, (r, -c))
		d[l, r] = min(d.get((l, r), INT_MAX), c)
		print(min(ml[1] - mr[1], d.get((ml[0], mr[0]), INT_MAX)))


import sys
input = sys.stdin.readline
inf = 11000000000.0
t = int(input())
for i in range(t):
	n = int(input())
	s = [inf, inf]
	e = [-inf, -inf]
	o = [-inf, -inf]
	for i in range(n):
		(l, r, c) = map(int, input().split())
		s = min(s, [l, c])
		e = max(e, [r, -c])
		o = max(o, [r - l, -c])
		ans = s[1] - e[1]
		if e[0] - s[0] == o[0]:
			ans = min(ans, -o[1])
		print(str(ans))


out = []
t = int(input())
for _ in range(t):
	n = int(input())
	l = (10 ** 10, 0)
	r = (-10 ** 10, 0)
	seen = dict()
	for i in range(n):
		(li, ri, ci) = map(int, input().split())
		if (li, ri) not in seen:
			seen[li, ri] = 10 ** 10
		seen[li, ri] = min(seen[li, ri], ci)
		l = min(l, (li, ci))
		r = max(r, (ri, -ci))
		p = [l[1] - r[1]]
		if (l[0], r[0]) in seen:
			p.append(seen[l[0], r[0]])
		out.append(min(p))
print('\n'.join(map(str, out)))


from collections import Counter, defaultdict, deque
import heapq
import bisect
from sys import stdin, stdout
from itertools import repeat
import math, random

def inp(force_list=False):
	re = list(map(int, input().split()))
	if len(re) == 1 and (not force_list):
		return re[0]
	return re

def inst():
	return input().strip()

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
mod = 1000000007

def my_main():
	kase = inp()
	pans = []
	mx = int(1e+17)
	for ka in range(kase):
		n = inp()
		da = [inp() for i in range(n)]
		ans = [str(da[0][-1])]
		(mx, mi) = (0, 0)
		tt = 0
		for ii in range(1, n):
			(l, r, c) = da[ii]
			if l < da[mi][0] or (l == da[mi][0] and c < da[mi][-1]):
				mi = ii
			if r > da[mx][1] or (r == da[mx][1] and c < da[mx][-1]):
				mx = ii
			if l <= da[tt][0] and r >= da[tt][1]:
				if l == da[tt][0] and r == da[tt][1] and (c >= da[tt][-1]):
					pass
				else:
					tt = ii
			cost = da[mx][-1] + da[mi][-1]
			if da[tt][0] == da[mi][0] and da[tt][1] == da[mx][1]:
				cost = min(cost, da[tt][-1])
			ans.append(str(cost))
		pans.append('\n'.join(ans))
	print('\n'.join(pans))
my_main()


def intshop(arr):
	minleft = float('inf')
	maxright = 0
	maxlen = 0
	costl = 0
	costr = 0
	costlen = 0
	for i in range(len(arr)):
		(l, r, c) = (arr[i][0], arr[i][1], arr[i][2])
		if l < minleft:
			minleft = l
			costl = c
		elif minleft == l:
			costl = min(costl, c)
		if maxright < r:
			maxright = r
			costr = c
		elif maxright == r:
			costr = min(costr, c)
		if maxlen < r - l + 1:
			maxlen = r - l + 1
			costlen = c
		elif maxlen == r - l + 1:
			costlen = min(costlen, c)
		cost = costl + costr
		if maxlen == maxright - minleft + 1:
			cost = min(cost, costlen)
		print(cost)
t = int(input())
while t:
	n = int(input())
	res = []
	while n:
		arr = list(map(int, input().split()))
		res.append(arr)
		n -= 1
	intshop(res)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	low = [10000000000, 10000000000]
	high = [0, 1000000000]
	both = [10000000000, 0, 1000000000]
	res = [0 for i in range(n)]
	for i in range(n):
		(l, r, c) = map(int, input().split())
		if l < low[0]:
			low[0] = l
			low[1] = c
		elif l == low[0]:
			if c < low[1]:
				low[1] = c
		if r > high[0]:
			high[0] = r
			high[1] = c
		elif r == high[0]:
			if c < high[1]:
				high[1] = c
		if l == low[0] and r == high[0]:
			if l == both[0] and r == both[1]:
				if both[2] > c:
					both[2] = c
			else:
				both[0] = l
				both[1] = r
				both[2] = c
		res[i] = low[1] + high[1]
		if low[0] == both[0] and high[0] == both[1]:
			res[i] = min(res[i], both[2])
	for i in res:
		print(i)


t = int(input())
for i in range(t):
	n = int(input())
	lefts = []
	rights = []
	costs = []
	ans = []
	for j in range(n):
		(l, r, c) = map(int, input().split())
		lefts.append(l)
		rights.append(r)
		costs.append(c)
	mni = 0
	mxi = 0
	starts = {}
	singles = {}
	for i in range(n):
		singles[rights[i] - lefts[i] + 1] = min(singles.get(rights[i] - lefts[i] + 1, 1 << 62), costs[i])
		if (lefts[mni], costs[mni]) > (lefts[i], costs[i]):
			mni = i
		if (-rights[mxi], costs[mxi]) > (-rights[i], costs[i]):
			mxi = i
		if costs[mni] + costs[mxi] <= singles.get(rights[mxi] - lefts[mni] + 1, 1 << 62):
			ans.append(costs[mni] + costs[mxi])
		else:
			ans.append(singles[rights[mxi] - lefts[mni] + 1])
	print('\n'.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	x = [list(map(int, input().split())) for i in range(n)]
	costl = x[0][2]
	costr = x[0][2]
	l = x[0][0]
	r = x[0][1]
	L = r - l
	costL = x[0][2]
	print(x[0][2])
	for i in x[1:]:
		(a, b, c) = i
		if a < l or (a == l and c < costl):
			costl = c
			l = a
		if b > r or (b == r and c < costr):
			costr = c
			r = b
		if b - a > L or (b - a == L and c < costL):
			costL = c
			L = b - a
		if r - l < L:
			print(costL)
		elif r - l == L:
			print(min(costl + costr, costL))
		else:
			print(costl + costr)


from math import gcd, sqrt
from functools import cmp_to_key
from string import ascii_lowercase as alph
import os, sys
from itertools import permutations
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt')
	sys.stdout = open('output.txt', 'w')
INF = float('inf')

def readList():
	return [int(i) for i in input().strip().split()]

def solve():
	n = int(input())
	a = []
	for i in range(n):
		(l, r, c) = readList()
		a.append([l, r, c])
	(curL, curR) = (a[0][0], a[0][1])
	cost = [a[0][2]] * 3
	s = 0
	while s < n:
		(l, r, c) = a[s]
		if l < curL:
			curL = l
			cost[0] = c
			if r >= curR:
				cost[2] = c
			else:
				cost[2] = INF
		if r > curR:
			curR = r
			cost[1] = c
			if l <= curL:
				cost[2] = c
			else:
				cost[2] = INF
		if l == curL:
			cost[0] = min(cost[0], c)
		if r == curR:
			cost[1] = min(cost[1], c)
		if l == curL and r == curR:
			cost[2] = min(cost[2], c)
		print(min(cost[0] + cost[1], cost[2]))
		s += 1

def test(t):
	while t:
		t -= 1
		solve()
t = int(input())
test(t)


import sys
input = sys.stdin.readline
inf = 11000000000.0
t = int(input())
while t > 0:
	n = int(input())
	(ml, cl) = (inf, inf)
	(mr, cr) = (0, inf)
	(maxlen, clen) = (0, inf)
	for i in range(n):
		(l, r, c) = map(int, input().split())
		if l < ml:
			ml = l
			cl = inf
		if l == ml:
			cl = min(cl, c)
		if r > mr:
			mr = r
			cr = inf
		if r == mr:
			cr = min(cr, c)
		if maxlen < r - l + 1:
			maxlen = r - l + 1
			clen = inf
		if maxlen == r - l + 1:
			clen = min(clen, c)
		ans = cl + cr
		if maxlen == mr - ml + 1:
			ans = min(ans, clen)
		print(ans)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	segs = []
	for i in range(n):
		segs.append(tuple(map(int, input().split())))
	min_index = 0
	max_index = 0
	coast_to_coast = 0
	ans = [segs[0][2]]
	for i in range(1, len(segs)):
		if segs[i][0] < segs[min_index][0] or (segs[i][0] == segs[min_index][0] and segs[i][2] < segs[min_index][2]):
			min_index = i
		if segs[i][1] > segs[max_index][1] or (segs[i][1] == segs[max_index][1] and segs[i][2] < segs[max_index][2]):
			max_index = i
		if segs[i][0] == segs[min_index][0] and segs[i][1] == segs[max_index][1]:
			if coast_to_coast == -1 or (segs[coast_to_coast][0] != segs[min_index][0] or segs[coast_to_coast][1] != segs[max_index][1]) or segs[coast_to_coast][2] > segs[i][2]:
				coast_to_coast = i
		res = segs[min_index][2] + segs[max_index][2]
		if segs[coast_to_coast][0] != segs[min_index][0] or segs[coast_to_coast][1] != segs[max_index][1]:
			coast_to_coast = -1
		if coast_to_coast != -1:
			res = min(res, segs[coast_to_coast][2])
		ans.append(res)
	print('\n'.join(map(str, ans)))


for i in range(int(input())):
	n = int(input())
	s = [[int(i) for i in input().split()] for _ in range(n)]
	mini = s[0]
	maxi = s[0]
	c = s[0]
	for i in s:
		if i[0] == mini[0] and i[2] <= mini[2] or i[0] < mini[0]:
			mini = i
		if i[1] == maxi[1] and i[2] <= maxi[2] or i[1] > maxi[1]:
			maxi = i
		if i[0] < c[0] or i[1] > c[1]:
			c = i
		elif c[0] == i[0] and c[1] == i[1] and (c[2] > i[2]):
			c = i
		if mini[0] < c[0] or maxi[1] > c[1]:
			print(mini[2] + maxi[2])
		elif c[0] == mini[0] and c[1] == maxi[1]:
			print(min(c[2], mini[2] + maxi[2]))
		else:
			print(c[2])


import sys
inp = sys.stdin.readline
inf = int(9000000000.0)
t = int(inp())
for i in range(t):
	n = int(inp())
	rr = [-inf, -inf]
	ll = [inf, inf]
	mxl = [-inf, -inf]
	for j in range(n):
		(a, b, c) = [int(x) for x in inp().split()]
		rr = max(rr, [b, -c])
		ll = min(ll, [a, c])
		mxl = max(mxl, [b - a + 1, -c])
		a1 = abs(rr[1]) + abs(ll[1])
		a2 = abs(mxl[1])
		if mxl[0] == rr[0] - ll[0] + 1:
			print(min(a1, a2))
		else:
			print(a1)


from collections import defaultdict
for j in range(int(input())):
	n = int(input())
	(ml, mr) = (10000000000, -1)
	(lc, lr) = (10000000000, 100000000000)
	dicl = defaultdict(lambda : 100000000000)
	dicr = defaultdict(lambda : 100000000000)
	dic = defaultdict(lambda : 100000000000)
	ans = []
	for i in range(n):
		(l, r, c) = list(map(int, input().split()))
		if ml == l:
			lc = min(lc, c)
		if mr == r:
			lr = min(lr, c)
		if l < ml:
			ml = l
			lc = c
		if mr < r:
			mr = r
			lr = c
		dic[l, r] = min(dic[l, r], c)
		mi = lc + lr
		mi = min(dic[ml, mr], mi)
		ans.append(mi)
	for i in ans:
		print(i)


def check(t1, t2, c):
	if t1 != t2:
		return c[t1] + c[t2]
	else:
		return c[t1]
for _ in range(int(input())):
	n = int(input())
	(l, r, c) = ([0] * n, [0] * n, [0] * n)
	for i in range(n):
		(x, y, z) = map(int, input().split())
		l[i] = x
		r[i] = y
		c[i] = z
	(t1, t2, t3) = (0, 0, 0)
	for i in range(n):
		if l[i] < l[t1] or (l[i] == l[t1] and c[i] < c[t1]):
			t1 = i
		if r[i] > r[t2] or (r[i] == r[t2] and c[i] < c[t2]):
			t2 = i
		if l[i] < l[t3] or r[i] > r[t3] or (l[i] == l[t3] and r[i] == r[t3] and (c[i] < c[t3])):
			t3 = i
		if l[t3] <= l[t1] and r[t3] >= r[t2] and (l[t3] < l[t1] or r[t3] > r[t2] or c[t3] < check(t1, t2, c)):
			print(c[t3])
		else:
			print(check(t1, t2, c))


out = []
t = int(input())
for _ in range(t):
	n = int(input())
	d = {}
	left = (float('inf'), 0)
	right = (float('-inf'), 0)
	for _ in range(n):
		(l, r, c) = map(int, input().split())
		if (l, r) not in d:
			d[l, r] = float('inf')
		d[l, r] = min(d[l, r], c)
		left = min(left, (l, c))
		right = max(right, (r, -c))
		p = [left[1] - right[1]]
		if (left[0], right[0]) in d:
			p.append(d[left[0], right[0]])
		out.append(min(p))
print(*out, sep='\n')


def hr(i, j, ct):
	return ct[i] if i == j else ct[i] + ct[j]
for _ in range(int(input())):
	n = int(input())
	lt = [0 for _ in range(n)]
	rt = [0 for _ in range(n)]
	ct = [0 for _ in range(n)]
	for i in range(n):
		(lt[i], rt[i], ct[i]) = map(int, input().split())
	i = j = k = 0
	for z in range(n):
		if lt[z] < lt[i] or (lt[z] == lt[i] and ct[z] < ct[i]):
			i = z
		if rt[z] > rt[j] or (rt[z] == rt[j] and ct[z] < ct[j]):
			j = z
		if lt[z] < lt[k] or rt[z] > rt[k] or (lt[z] == lt[k] and rt[z] == rt[k] and (ct[z] < ct[k])):
			k = z
		if lt[k] <= lt[i] and rt[k] >= rt[j] and (lt[k] < lt[i] or rt[k] > rt[j] or ct[k] < hr(i, j, ct)):
			print(ct[k])
		else:
			print(hr(i, j, ct))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	(p, q, a) = (0, 0, 0)
	for i in range(n):
		(l, r, c) = arr[i]
		if l < arr[p][0] or (l == arr[p][0] and c < arr[p][2]):
			p = i
		if r > arr[q][1] or (r == arr[q][1] and c < arr[q][2]):
			q = i
		if l < arr[a][0] or r > arr[a][1] or (l == arr[a][0] and r == arr[a][1] and (c < arr[a][2])):
			a = i
		cost = arr[p][2] + arr[q][2] - int(p == q) * arr[p][2]
		if arr[a][0] <= arr[p][0] and arr[a][1] >= arr[q][1] and (arr[a][0] < arr[p][0] or arr[a][1] > arr[q][1] or arr[a][2] < cost):
			print(arr[a][2])
		else:
			print(cost)


import sys
for _ in range(int(input())):
	n = int(input())
	a = []
	best_l = 1e+17
	best_r = -1
	best_l_cost = 1e+17
	best_r_cost = 1e+17
	for _ in range(n):
		a.append(list(map(int, input().split())))
	o = {}
	for i in range(n):
		item = a[i]
		if item[0] < best_l:
			best_l = item[0]
			best_l_cost = item[2]
		if item[0] == best_l:
			best_l_cost = min(best_l_cost, item[2])
		if item[1] > best_r:
			best_r = item[1]
			best_r_cost = item[2]
		if item[1] == best_r:
			best_r_cost = min(best_r_cost, item[2])
		if o.get((item[0], item[1])):
			o[item[0], item[1]] = min(o[item[0], item[1]], item[2])
		else:
			o[item[0], item[1]] = item[2]
		k = o.get((best_l, best_r))
		if k == None:
			k = 1e+17
		print(min(best_l_cost + best_r_cost, k))


import math, bisect, heapq, random, sys, itertools
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p = 10 ** 9 + 7
for t in range(int(input())):
	(n,) = ints()
	query = [ints() for i in range(n)][::-1]
	(l, r, c) = query.pop()
	ANS = []
	ANS.append(c)
	(cl, cr) = (c, c)
	(L, R) = (l, r)
	(left, right, rg) = ({}, {}, {})
	left[l] = c
	right[r] = c
	rg[l, r] = c
	for i in range(n - 1):
		(l, r, c) = query.pop()
		if l not in left:
			left[l] = p
		left[l] = min(left[l], c)
		if r not in right:
			right[r] = p
		right[r] = min(right[r], c)
		if (l, r) not in rg:
			rg[l, r] = p
		rg[l, r] = min(rg[l, r], c)
		L = min(l, L)
		R = max(r, R)
		ans = left[L] + right[R]
		if (L, R) in rg:
			ans = min(rg[L, R], ans)
		ANS.append(ans)
	print(*ANS, sep='\n')


from heapq import heappush, heappop
ans = []
for _ in range(int(input())):
	(lheap, rheap, all) = ([], [], [])
	for i in range(int(input())):
		(l, r, c) = map(int, input().split())
		heappush(lheap, (l, c, r))
		heappush(rheap, (-r, c, l))
		heappush(all, (l - r, c, l, r))
		left = lheap[0][0]
		lc = lheap[0][1]
		right = -rheap[0][0]
		rc = rheap[0][1]
		(la, ra) = (all[0][2], all[0][3])
		if (la, ra) == (left, right) and all[0][1] < lc + rc:
			ans.append(all[0][1])
		else:
			ans.append(lc + rc)
print(*ans, sep='\n')


import math
for i in range(int(input())):
	n = int(input())
	mi = 2000101001
	ma = -1
	c = []
	cost = 2000101001
	mind = -1
	maxd = -1
	ans = []
	prev = [2000101001, -1]
	for j in range(n):
		arr = list(map(int, input().split()))
		c.append(arr[2])
		mi = min(mi, arr[0])
		ma = max(ma, arr[1])
		if prev[0] == arr[0]:
			if c[-1] < c[mind]:
				mind = j
		elif arr[0] < prev[0]:
			mind = j
		if prev[1] == arr[1]:
			if c[-1] < c[maxd]:
				maxd = j
		elif arr[1] > prev[1]:
			maxd = j
		if [mi, ma] == prev:
			if mi == arr[0] and ma == arr[1]:
				cost = min(cost, arr[2], c[mind] + c[maxd])
			else:
				cost = min(cost, c[mind] + c[maxd])
		elif mi == arr[0] and ma == arr[1]:
			cost = min(arr[2], c[mind] + c[maxd])
		else:
			cost = c[mind] + c[maxd]
		prev = [mi, ma]
		ans.append(cost)
	for j in ans:
		print(j)


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for i in range(int(input())):
	n = int(input())
	(l, r, c) = int_arr()
	d = {}
	d[l] = c
	d[r] = c
	d[l, r] = c
	mn_l = l
	mn_r = r
	print(c)
	for i in range(n - 1):
		(l, r, c) = int_arr()
		d[l] = min(c, d.get(l, float('inf')))
		d[r] = min(c, d.get(r, float('inf')))
		d[l, r] = min(c, d.get((l, r), float('inf')))
		mn_l = min(mn_l, l)
		mn_r = max(mn_r, r)
		ans = min(d[mn_l] + d[mn_r], d.get((mn_l, mn_r), float('inf')))
		print(ans)


import sys
fast = lambda : sys.stdin.readline()

def ans():
	n = int(fast())
	HashMap = {}
	arr = []
	minimum_val = float('inf')
	maximum_val = -float('inf')
	result = []
	for _ in range(n):
		(a, b, c) = [int(x) for x in fast().split()]
		minimum_val = min(a, minimum_val)
		maximum_val = max(b, maximum_val)
		arr.append([a, b, c])
		if a not in HashMap:
			HashMap[a] = c
		else:
			HashMap[a] = min(HashMap[a], c)
		if b not in HashMap:
			HashMap[b] = c
		else:
			HashMap[b] = min(HashMap[b], c)
		if (a, b) not in HashMap:
			HashMap[a, b] = c
		else:
			HashMap[a, b] = min(HashMap[a, b], c)
		result.append(min(HashMap[minimum_val] + HashMap[maximum_val], HashMap.get((minimum_val, maximum_val), float('inf'))))
	for i in result:
		print(i)
for _ in range(int(fast())):
	ans()


sI = lambda : input()
iI = lambda : int(input())
mI = lambda : map(int, input().split())
lI = lambda : list(mI())
for i in range(iI()):
	n = iI()
	(l, r, c) = ([], [], [])
	for i in range(n):
		(a, b, g) = mI()
		l.append(a)
		r.append(b)
		c.append(g)
	ans = [c[0]]
	d = {}
	d[l[0], r[0]] = c[0]
	mn = 0
	mx = 0
	for i in range(1, n):
		if (l[i], r[i]) not in d:
			d[l[i], r[i]] = c[i]
		d[l[i], r[i]] = min(c[i], d[l[i], r[i]])
		if l[i] < l[mn] or (l[i] == l[mn] and c[i] < c[mn]):
			mn = i
		if r[i] > r[mx] or (r[i] == r[mx] and c[i] < c[mx]):
			mx = i
		ans1 = c[mx] + c[mn]
		ans1 = min(ans1, d.get((l[mn], r[mx]), 10 ** 15))
		ans.append(ans1)
	for i in ans:
		print(i)


class ValCost:

	def __init__(self, val, cost):
		self.val = val
		self.cost = cost

def main():
	T = int(input())
	for _ in range(T):
		n = int(input())
		segments = []
		for j in range(n):
			(l, r, c) = [int(x) for x in input().split(' ')]
			segments.append([l, r, c])
		cost = segments[0][2]
		min1 = ValCost(segments[0][0], cost)
		max1 = ValCost(segments[0][1], cost)
		longest = ValCost(segments[0][1] - segments[0][0], cost)
		print(cost)
		for i in range(1, len(segments)):
			segment = segments[i]
			(l, r, c) = segment
			if l == min1.val:
				min1.cost = min(min1.cost, c)
			if r == max1.val:
				max1.cost = min(max1.cost, c)
			if l < min1.val:
				min1 = ValCost(l, c)
			if r > max1.val:
				max1 = ValCost(r, c)
			if r - l == longest.val:
				longest.cost = min(longest.cost, c)
			if r - l > longest.val:
				longest = ValCost(r - l, c)
			best = min1.cost + max1.cost
			if longest.val == max1.val - min1.val:
				print(min(longest.cost, best))
			else:
				print(best)
main()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri, shuffle
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	n = ip()
	arr = []
	cur_min = float('inf')
	cur_max = -float('inf')
	dic = dd(lambda : float('inf'))
	cost = dd(lambda : float('inf'))
	ch = set()
	for i in range(n):
		(l, r, c) = inp()
		ch.add((l, r))
		cost[l, r] = min(cost[l, r], c)
		dic[l] = min(dic[l], c)
		dic[r] = min(dic[r], c)
		cur_min = min(cur_min, l)
		cur_max = max(cur_max, r)
		if (cur_min, cur_max) in ch:
			ans = min(cost[cur_min, cur_max], dic[cur_min] + dic[cur_max])
		else:
			ans = dic[cur_min] + dic[cur_max]
		print(ans)


import collections
import sys
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	n = int(fast())
	dito = collections.defaultdict(lambda : float('inf'))
	arr = []
	mini = float('inf')
	maxi = -1
	for i in range(n):
		(a, b, c) = [int(x) for x in fast().split()]
		mini = min(a, mini)
		maxi = max(b, maxi)
		arr.append([a, b, c])
		dito[a] = min(dito[a], c)
		dito[b] = min(dito[b], c)
		dito[a, b] = min(dito[a, b], c)
		print(min(dito[mini] + dito[maxi], dito.get((mini, maxi), float('inf'))))
	return
for _ in range(test_case):
	ans()


import sys
input = sys.stdin.readline
from pprint import pprint
import math
INF = 1 << 63

def do():
	from collections import defaultdict
	specialcost = defaultdict(lambda : defaultdict(lambda : INF))
	cost = defaultdict(lambda : INF)
	n = int(input())
	dat = []
	for _ in range(n):
		dat.append(map(int, input().split()))
	(curl, curr) = (INF, -INF)
	for i in range(n):
		(l, r, c) = dat[i]
		specialcost[l][r] = min(specialcost[l][r], c)
		(curl, curr) = (min(l, curl), max(r, curr))
		(cost[l], cost[r]) = (min(cost[l], c), min(cost[r], c))
		print(min(cost[curl] + cost[curr], specialcost[curl][curr]))
q = int(input())
for _ in range(q):
	do()


t = int(input())
for i in range(t):
	n = int(input())
	(low, high, cost) = [int(k) for k in input().split()]
	lowcost = cost
	highcost = cost
	print(cost)
	for j in range(n - 1):
		(l, r, c) = [int(k) for k in input().split()]
		if low > l and high < r:
			lowcost = c
			highcost = c
			cost = c
			low = l
			high = r
		elif low > l:
			lowcost = c
			low = l
			if r == high:
				cost = c
				if highcost > c:
					highcost = c
			else:
				cost = lowcost + highcost
		elif high < r:
			highcost = c
			high = r
			if l == low:
				cost = c
				if lowcost > c:
					lowcost = c
			else:
				cost = lowcost + highcost
		elif low == l and high == r:
			if cost > c:
				cost = c
				if highcost > c:
					highcost = c
				if lowcost > c:
					lowcost = c
		elif low == l:
			if lowcost > c:
				lowcost = c
			if lowcost + highcost < cost:
				cost = lowcost + highcost
		elif high == r:
			if highcost > c:
				highcost = c
			if lowcost + highcost < cost:
				cost = lowcost + highcost
		print(cost)


def main():
	from math import inf
	t = int(input())
	for i in range(t):
		n = int(input())
		lf = [inf, -1]
		rt = [-1, -1]
		one = [inf, -1, -1]
		for i in range(n):
			(l, r, c) = map(int, input().split())
			if l < lf[0] or (l == lf[0] and c < lf[1]):
				lf = [l, c]
			if r > rt[0] or (r == rt[0] and c < rt[1]):
				rt = [r, c]
			if l < one[0] or r > one[1] or (l == one[0] and r == one[1] and (c < one[2])):
				one = [l, r, c]
			if one[0] < lf[0] or one[1] > rt[0] or (lf[0] == one[0] and rt[0] == one[1] and (lf[1] + rt[1] > one[2])):
				print(one[2])
			else:
				print(lf[1] + rt[1])
main()


import math
import sys
import queue
from heapq import heappop, heappush
import random

def solve():
	n = int(input())
	(left_min, right_max, cost) = map(int, input().split())
	max_r = right_max - left_min
	print(cost)
	left_cost = cost
	right_cost = cost
	for i in range(n - 1):
		(l, r, c) = map(int, input().split())
		if r - l == max_r:
			cost = min(cost, c)
		if r - l > max_r:
			max_r = r - l
			cost = c
		if r >= right_max:
			if r == right_max:
				right_cost = min(right_cost, c)
			else:
				(right_max, right_cost) = (r, c)
		if l <= left_min:
			if l == left_min:
				left_cost = min(left_cost, c)
			else:
				(left_min, left_cost) = (l, c)
		if right_max - left_min > max_r:
			cost = left_cost + right_cost
		if right_max - left_min == max_r:
			cost = min(cost, left_cost + right_cost)
		print(cost)
multi_test = 1
if multi_test:
	t = int(input())
	for _ in range(t):
		solve()
else:
	solve()


t = int(input())
one = 1
zero = 0
import heapq
for _ in range(t):
	n = int(input())
	lrc = []
	for i in range(n):
		lrc.append([int(x) for x in input().split()])
	one *= 1
	zero += 0
	l_heap = []
	r_heap = []
	lr_cost = dict()
	for i in range(n):
		heapq.heappush(l_heap, (lrc[i][0], lrc[i][2]))
		heapq.heappush(r_heap, (-lrc[i][1], lrc[i][2]))
		if (lrc[i][0], lrc[i][1]) in lr_cost:
			lr_cost[lrc[i][0], lrc[i][1]] = min(lr_cost[lrc[i][0], lrc[i][1]], lrc[i][2])
		else:
			lr_cost[lrc[i][0], lrc[i][1]] = lrc[i][2]
			one *= 1
			zero += 0
		Min = l_heap[0][1] + r_heap[0][1]
		if (l_heap[0][0], -r_heap[0][0]) in lr_cost:
			Min = min(Min, lr_cost[l_heap[0][0], -r_heap[0][0]])
			one *= 1
			zero += 0
		print(Min)


for iii in range(int(input())):
	minn = 98765432456
	maxx = -456789867564
	lenn = -1
	lenncost = 987654321
	minncost = 987654321
	maxxcost = 12345678998765432
	for jjj in range(int(input())):
		(a, b, c) = map(int, input().split())
		if a == minn and minncost >= c:
			minncost = c
		elif a < minn:
			minn = a
			minncost = c
		if b == maxx and maxxcost >= c:
			maxxcost = c
		elif b > maxx:
			maxx = b
			maxxcost = c
		if b - a == lenn and lenncost >= c:
			lenncost = c
		elif b - a > lenn:
			lenn = b - a
			lenncost = c
		if maxx - minn == lenn:
			if lenncost <= maxxcost + minncost:
				print(lenncost)
			else:
				print(maxxcost + minncost)
		else:
			print(minncost + maxxcost)


def solve():
	smallest = 10 ** 10
	bigest = -10 ** 10
	tien_a = 0
	tien_b = 0
	tien_row = 10 ** 10
	k = 0
	max_d = -10 ** 10
	for i in range(int(input())):
		(a, b, m) = map(int, input().split())
		if a < smallest:
			smallest = a
			tien_a = m
			max_d = bigest - smallest + 1
			tien_row = 10 ** 10
		if b > bigest:
			bigest = b
			tien_b = m
			max_d = bigest - smallest + 1
			tien_row = 10 ** 10
		if a == smallest and m < tien_a:
			tien_a = m
		if b == bigest and m < tien_b:
			tien_b = m
		if b - a + 1 >= max_d:
			max_d = b - a + 1
			tien_row = min(tien_row, m)
		print(min(tien_a + tien_b, tien_row))
for i in range(int(input())):
	solve()


def solve():
	n = int(input())
	valL = 0
	valR = 0
	mxN = 0
	mnval = 0
	for i in range(0, n):
		(l, r, c) = map(int, input().split())
		if i == 0:
			mnL = l
			mxR = r
			valL = c
			valR = c
			mxN = r - l + 1
			mnval = c
			print(c)
			continue
		if l < mnL:
			mnL = l
			valL = c
		elif l == mnL:
			valL = min(valL, c)
		if r > mxR:
			mxR = r
			valR = c
		elif r == mxR:
			valR = min(valR, c)
		if r - l + 1 > mxN:
			mxN = r - l + 1
			mnval = c
		elif r - l + 1 == mxN:
			mnval = min(mnval, c)
		ans = valL + valR
		if mxR - mnL + 1 == mxN:
			ans = min(ans, mnval)
		print(ans)
t = int(input())
while t:
	solve()
	t -= 1


maxval = 10 ** 9 + 1
T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	low = maxval
	high = 0
	bestlow = maxval
	besthigh = maxval
	bestbothcost = maxval
	bestbothcandidate = False
	for s in range(n):
		(l, r, c) = list(map(int, input().split()))
		if l < low:
			low = l
			bestlow = c
			bestbothcost = maxval
			bestbothcandidate = False
		elif l == low:
			if c < bestlow:
				bestlow = c
		if r > high:
			high = r
			besthigh = c
			bestbothcost = maxval
			bestbothcandidate = False
		elif r == high:
			if c < besthigh:
				besthigh = c
		if l == low and r == high:
			if c < bestbothcost:
				bestbothcost = c
				bestbothcandidate = True
		if bestbothcandidate:
			if bestbothcost < bestlow + besthigh:
				print(bestbothcost)
			else:
				bestbothcandidate = False
				print(bestlow + besthigh)
		else:
			print(bestlow + besthigh)


import math
for _ in range(int(input())):
	n = int(input())
	l = math.inf
	h = 0
	c = 0
	h_cost = 0
	ph = 0
	l_cost = 0
	lh = 0
	ans = []
	for q in range(n):
		(L, R, C) = list(map(int, input().split()))
		if l > L and h < R:
			c = C
			l_cost = C
			h_cost = C
			l = L
			h = R
		elif l > L:
			l = L
			l_cost = C
			if h == R:
				c = C
				h_cost = min(h_cost, C)
			else:
				c = l_cost + h_cost
		elif R > h:
			h = R
			h_cost = C
			if l == L:
				c = C
				l_cost = min(l_cost, C)
			else:
				c = l_cost + h_cost
		elif l == L and h == R:
			l_cost = min(l_cost, C)
			h_cost = min(h_cost, C)
			c = min(C, c)
		elif l == L:
			l_cost = min(l_cost, C)
			c = min(c, l_cost + h_cost)
		elif h == R:
			h_cost = min(h_cost, C)
			c = min(c, l_cost + h_cost)
		print(c)


for pratyush in range(int(input())):
	m = float('inf')
	lc = float('inf')
	mc = float('inf')
	xc = float('inf')
	(x, l) = (0, -1)
	for i in range(int(input())):
		(a, b, c) = map(int, input().split())
		if a == m and mc >= c:
			mc = c
		elif a < m:
			(m, mc) = (a, c)
		if b == x and xc >= c:
			xc = c
		elif b > x:
			(x, xc) = (b, c)
		if b - a == l and lc >= c:
			lc = c
		elif b - a > l:
			(l, lc) = (b - a, c)
		if x - m == l:
			if lc <= xc + mc:
				print(lc)
			else:
				print(xc + mc)
		else:
			print(mc + xc)