김밥

김밥은 소금과 참기름으로 간을 한 밥에 속재료를 얹어 김으로 말고, 한입 크기로 썰어 낸 음식이다. 포장이 간편하고 휴대하기 쉬우며 특별한 도구 없이 손으로 집어 먹을 수 있어서, 바쁜 아침 출근길에 간편하게 먹기 좋고 나들이용 도시락으로도 인기가 많다. 기본 줄김밥에는 달걀, 햄, 당근, 단무지, 맛살, 오이, 우엉, 어묵 등이 들어가며, 그 밖의 특별한 재료가 들어가면 재료 이름을 따서 김밥 이름을 붙인다. 이렇게 파생된 김밥 중 시중에서 흔히 팔리는 것으로는 참치김밥, 치즈김밥, 소고기김밥, 김치김밥, 멸치김밥, 콩나물김밥 등이 있다. 아보카도, 파인애플, 아스파라거스, 망고처럼 다소 이국적인 재료를 넣은 김밥도 있으며, 요리 연구가들은 최근 국내에 소개된 다양한 식재료를 김밥에 접목하는 시도를 하고 있다.

(출처: 위키백과)

[그림 1] 김밥을 말기 위해 김 위에 식재료를 얹은 모습

당신은 세계 최고의 김밥 장인입니다. 당신 앞에는 수직선상의 구간으로 나타낼 수 있는 $N$개의 식재료가 놓여 있고, 오늘도 김밥을 말아야 합니다. 세계 최고 타이틀을 가진 당신을 검증하기 위한 미션이 주어졌습니다. 식재료의 좌우 위치를 바꾸지 않으면서 가장 맛있는 김밥 한 줄을 마는 것입니다.

김밥을 말려면 [그림 1]처럼 김 위에 다른 식재료가 모두 얹힌 형태가 되어야 합니다. 즉, 수직선상에서 김이 김밥을 구성하는 다른 모든 식재료를 포함해야 합니다. 원래 김밥은 김으로 말지만, 여기서는 가장 맛있는 김밥을 만드는 것이 중요하므로 어떤 식재료로 말아도 상관없습니다. 다시 말해, 수직선상에서 고른 식재료 중 하나가 고른 다른 모든 식재료를 포함해야 합니다. 수직선상에서 식재료 $S$가 식재료 $T$를 포함한다는 것은 $S$의 구간이 $[l_S, r_S]$, $T$의 구간이 $[l_T, r_T]$일 때 $l_S \leq l_T$이고 $r_T \leq r_S$인 것입니다.

식재료 하나로만 구성된 김밥을 마는 것도 가능합니다. 김밥의 맛은 김밥에 속한 각 식재료의 맛을 모두 더한 값이며, 맛이 클수록 맛있는 김밥입니다. 가장 맛있는 김밥을 말아 세계 최고의 김밥 장인임을 증명해 주세요!

첫째 줄에 식재료의 개수 $N$이 주어집니다. $(1 \leq N \leq 1\,000\,000)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 식재료의 구간과 맛을 나타내는 정수 $l_i$, $r_i$, $v_i$가 공백을 사이에 두고 차례로 주어집니다. 수직선상에서 $i$번째 식재료의 구간이 $[l_i, r_i]$이고 맛이 $v_i$임을 뜻합니다. $(-10^9 \leq l_i \leq r_i \leq 10^9$, $1 \leq v_i \leq 10^9)$

말 수 있는 가장 맛있는 김밥의 맛을 출력하세요.

김밥은 믿음직스럽습니다. 재료를 한눈에 볼 수 있어서 예상 밖의 식감이나 맛에 놀랄 일이 없습니다.