import sys
def solve():
# 標準入力から全てのデータを読み込み
input_tokens = sys.stdin.read().split()
if not input_tokens:
return
n = int(input_tokens[0])
# ジョブ情報をリストに格納 [開始時刻, 終了時刻, 価値]
jobs = []
idx = 1
for _ in range(n):
s = int(input_tokens[idx])
f = int(input_tokens[idx + 1])
v = int(input_tokens[idx + 2])
jobs.append([s, f, v])
idx += 3
# 1. 終了時刻で安定ソートを実行
jobs.sort(key=lambda x: x[1])
# 添字を1から扱うため、先頭にダミー要素を追加
sorted_jobs = [[-1, -1, 0]] + jobs
# 2. q(j) の計算
q = [0] * (n + 1)
for j in range(1, n + 1):
sj = sorted_jobs[j][0]
for i in range(j - 1, 0, -1):
if sorted_jobs[i][1] <= sj:
q[j] = i
break
# 3. OPT_j の計算 (動的計画法)
opt = [0] * (n + 1)
for j in range(1, n + 1):
vj = sorted_jobs[j][2]
# 漸化式: OPT_j = max(v_j + OPT_{q(j)}, OPT_{j-1})
include_j = vj + opt[q[j]]
exclude_j = opt[j - 1]
if include_j >= exclude_j: # 等しい場合はジョブを含める挙動に合わせる
opt[j] = include_j
else:
opt[j] = exclude_j
# 4. 最適解(ジョブの集合)の計算(バックトラッキング)
solution = []
curr = n
while curr > 0:
vj = sorted_jobs[curr][2]
# ジョブcurrを含めた場合の価値が、含めない場合(OPT_{curr-1})以上であれば採用
if vj + opt[q[curr]] >= opt[curr - 1]:
solution.append(curr)
curr = q[curr] # 重ならない直近のジョブへ移動
else:
curr -= 1 # ひとつ前のジョブを確認
# 指定された形式(降順リスト)で出力
print(solution)
if __name__ == "__main__":
solve()
aW1wb3J0IHN5cwoKZGVmIHNvbHZlKCk6CiAgICAjIOaomea6luWFpeWKm+OBi+OCieWFqOOBpuOBruODh+ODvOOCv+OCkuiqreOBv+i+vOOBvwogICAgaW5wdXRfdG9rZW5zID0gc3lzLnN0ZGluLnJlYWQoKS5zcGxpdCgpCiAgICBpZiBub3QgaW5wdXRfdG9rZW5zOgogICAgICAgIHJldHVybgogICAgCiAgICBuID0gaW50KGlucHV0X3Rva2Vuc1swXSkKICAgIAogICAgIyDjgrjjg6fjg5bmg4XloLHjgpLjg6rjgrnjg4jjgavmoLzntI0gW+mWi+Wni+aZguWIuywg57WC5LqG5pmC5Yi7LCDkvqHlgKRdCiAgICBqb2JzID0gW10KICAgIGlkeCA9IDEKICAgIGZvciBfIGluIHJhbmdlKG4pOgogICAgICAgIHMgPSBpbnQoaW5wdXRfdG9rZW5zW2lkeF0pCiAgICAgICAgZiA9IGludChpbnB1dF90b2tlbnNbaWR4ICsgMV0pCiAgICAgICAgdiA9IGludChpbnB1dF90b2tlbnNbaWR4ICsgMl0pCiAgICAgICAgam9icy5hcHBlbmQoW3MsIGYsIHZdKQogICAgICAgIGlkeCArPSAzCiAgICAKICAgICMgMS4g57WC5LqG5pmC5Yi744Gn5a6J5a6a44K944O844OI44KS5a6f6KGMCiAgICBqb2JzLnNvcnQoa2V5PWxhbWJkYSB4OiB4WzFdKQogICAgCiAgICAjIOa3u+Wtl+OCkjHjgYvjgonmibHjgYbjgZ/jgoHjgIHlhYjpoK3jgavjg4Djg5/jg7zopoHntKDjgpLov73liqAKICAgIHNvcnRlZF9qb2JzID0gW1stMSwgLTEsIDBdXSArIGpvYnMKICAgIAogICAgIyAyLiBxKGopIOOBruioiOeulwogICAgcSA9IFswXSAqIChuICsgMSkKICAgIGZvciBqIGluIHJhbmdlKDEsIG4gKyAxKToKICAgICAgICBzaiA9IHNvcnRlZF9qb2JzW2pdWzBdCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UoaiAtIDEsIDAsIC0xKToKICAgICAgICAgICAgaWYgc29ydGVkX2pvYnNbaV1bMV0gPD0gc2o6CiAgICAgICAgICAgICAgICBxW2pdID0gaQogICAgICAgICAgICAgICAgYnJlYWsKICAgIAogICAgIyAzLiBPUFRfaiDjga7oqIjnrpcgKOWLleeahOioiOeUu+azlSkKICAgIG9wdCA9IFswXSAqIChuICsgMSkKICAgIGZvciBqIGluIHJhbmdlKDEsIG4gKyAxKToKICAgICAgICB2aiA9IHNvcnRlZF9qb2JzW2pdWzJdCiAgICAgICAgIyDmvLjljJblvI86IE9QVF9qID0gbWF4KHZfaiArIE9QVF97cShqKX0sIE9QVF97ai0xfSkKICAgICAgICBpbmNsdWRlX2ogPSB2aiArIG9wdFtxW2pdXQogICAgICAgIGV4Y2x1ZGVfaiA9IG9wdFtqIC0gMV0KICAgICAgICAKICAgICAgICBpZiBpbmNsdWRlX2ogPj0gZXhjbHVkZV9qOiAjIOetieOBl+OBhOWgtOWQiOOBr+OCuOODp+ODluOCkuWQq+OCgeOCi+aMmeWLleOBq+WQiOOCj+OBm+OCiwogICAgICAgICAgICBvcHRbal0gPSBpbmNsdWRlX2oKICAgICAgICBlbHNlOgogICAgICAgICAgICBvcHRbal0gPSBleGNsdWRlX2oKICAgICAgICAgICAgCiAgICAjIDQuIOacgOmBqeino++8iOOCuOODp+ODluOBrumbhuWQiO+8ieOBruioiOeul++8iOODkOODg+OCr+ODiOODqeODg+OCreODs+OCsO+8iQogICAgc29sdXRpb24gPSBbXQogICAgY3VyciA9IG4KICAgIHdoaWxlIGN1cnIgPiAwOgogICAgICAgIHZqID0gc29ydGVkX2pvYnNbY3Vycl1bMl0KICAgICAgICAjIOOCuOODp+ODlmN1cnLjgpLlkKvjgoHjgZ/loLTlkIjjga7kvqHlgKTjgYzjgIHlkKvjgoHjgarjgYTloLTlkIgoT1BUX3tjdXJyLTF9KeS7peS4iuOBp+OBguOCjOOBsOaOoeeUqAogICAgICAgIGlmIHZqICsgb3B0W3FbY3Vycl1dID49IG9wdFtjdXJyIC0gMV06CiAgICAgICAgICAgIHNvbHV0aW9uLmFwcGVuZChjdXJyKQogICAgICAgICAgICBjdXJyID0gcVtjdXJyXSAjIOmHjeOBquOCieOBquOBhOebtOi/keOBruOCuOODp+ODluOBuOenu+WLlQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGN1cnIgLT0gMSAjIOOBsuOBqOOBpOWJjeOBruOCuOODp+ODluOCkueiuuiqjQogICAgICAgICAgICAKICAgICMg5oyH5a6a44GV44KM44Gf5b2i5byP77yI6ZmN6aCG44Oq44K544OI77yJ44Gn5Ye65YqbCiAgICBwcmludChzb2x1dGlvbikKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBzb2x2ZSgp