import sys
def solve():
# 入力データの読み込み
input_data = sys.stdin.read().split()
if not input_data:
return
n = int(input_data[0])
jobs = []
idx = 1
for i in range(n):
s = int(input_data[idx])
t = int(input_data[idx+1])
v = int(input_data[idx+2])
jobs.append({'s': s, 't': t, 'v': v})
idx += 3
# 1. 終了時刻 t で安定ソートを行う
# Pythonの sort() は安定ソートです
jobs.sort(key=lambda x: x['t'])
# 1-indexedで管理するため、先頭にダミーを追加
sorted_jobs = [{'s': 0, 't': 0, 'v': 0}] + jobs
# 2. p(j) の計算
p = [0] * (n + 1)
for j in range(1, n + 1):
for i in range(j - 1, 0, -1):
if sorted_jobs[i]['t'] <= sorted_jobs[j]['s']:
p[j] = i
break
# 3. 動的計画法 (DP) で各段階の最適値を計算
opt = [0] * (n + 1)
for j in range(1, n + 1):
# 漸化式: OPT(j) = max(v_j + OPT(p(j)), OPT(j-1))
val_include = sorted_jobs[j]['v'] + opt[p[j]]
val_exclude = opt[j-1]
if val_include >= val_exclude:
opt[j] = val_include
else:
opt[j] = val_exclude
# 4. 最適解(ジョブの集合)を求める
# スライドのアルゴリズムに従い、後ろから遡る
solution = []
curr = n
while curr > 0:
# 「そのジョブを選んだ場合」の値が、現在のOPT値と等しいかチェック
# 同点の場合は現在のジョブを選ぶ(条件: >= )
if sorted_jobs[curr]['v'] + opt[p[curr]] >= opt[curr-1]:
solution.append(curr)
curr = p[curr] # 直前の非競合ジョブへジャンプ
else:
curr -= 1 # 一つ前のジョブへ移動
# 出力例1, 2, 3 の形式に合わせてリストをそのまま出力
print(solution)
if __name__ == "__main__":
solve()
aW1wb3J0IHN5cwoKZGVmIHNvbHZlKCk6CiAgICAjIOWFpeWKm+ODh+ODvOOCv+OBruiqreOBv+i+vOOBvwogICAgaW5wdXRfZGF0YSA9IHN5cy5zdGRpbi5yZWFkKCkuc3BsaXQoKQogICAgaWYgbm90IGlucHV0X2RhdGE6CiAgICAgICAgcmV0dXJuCiAgICAKICAgIG4gPSBpbnQoaW5wdXRfZGF0YVswXSkKICAgIGpvYnMgPSBbXQogICAgaWR4ID0gMQogICAgZm9yIGkgaW4gcmFuZ2Uobik6CiAgICAgICAgcyA9IGludChpbnB1dF9kYXRhW2lkeF0pCiAgICAgICAgdCA9IGludChpbnB1dF9kYXRhW2lkeCsxXSkKICAgICAgICB2ID0gaW50KGlucHV0X2RhdGFbaWR4KzJdKQogICAgICAgIGpvYnMuYXBwZW5kKHsncyc6IHMsICd0JzogdCwgJ3YnOiB2fSkKICAgICAgICBpZHggKz0gMwoKICAgICMgMS4g57WC5LqG5pmC5Yi7IHQg44Gn5a6J5a6a44K944O844OI44KS6KGM44GGCiAgICAjIFB5dGhvbuOBriBzb3J0KCkg44Gv5a6J5a6a44K944O844OI44Gn44GZCiAgICBqb2JzLnNvcnQoa2V5PWxhbWJkYSB4OiB4Wyd0J10pCgogICAgIyAxLWluZGV4ZWTjgafnrqHnkIbjgZnjgovjgZ/jgoHjgIHlhYjpoK3jgavjg4Djg5/jg7zjgpLov73liqAKICAgIHNvcnRlZF9qb2JzID0gW3sncyc6IDAsICd0JzogMCwgJ3YnOiAwfV0gKyBqb2JzCgogICAgIyAyLiBwKGopIOOBruioiOeulwogICAgcCA9IFswXSAqIChuICsgMSkKICAgIGZvciBqIGluIHJhbmdlKDEsIG4gKyAxKToKICAgICAgICBmb3IgaSBpbiByYW5nZShqIC0gMSwgMCwgLTEpOgogICAgICAgICAgICBpZiBzb3J0ZWRfam9ic1tpXVsndCddIDw9IHNvcnRlZF9qb2JzW2pdWydzJ106CiAgICAgICAgICAgICAgICBwW2pdID0gaQogICAgICAgICAgICAgICAgYnJlYWsKCiAgICAjIDMuIOWLleeahOioiOeUu+azlSAoRFApIOOBp+WQhOautemajuOBruacgOmBqeWApOOCkuioiOeulwogICAgb3B0ID0gWzBdICogKG4gKyAxKQogICAgZm9yIGogaW4gcmFuZ2UoMSwgbiArIDEpOgogICAgICAgICMg5ry45YyW5byPOiBPUFQoaikgPSBtYXgodl9qICsgT1BUKHAoaikpLCBPUFQoai0xKSkKICAgICAgICB2YWxfaW5jbHVkZSA9IHNvcnRlZF9qb2JzW2pdWyd2J10gKyBvcHRbcFtqXV0KICAgICAgICB2YWxfZXhjbHVkZSA9IG9wdFtqLTFdCiAgICAgICAgCiAgICAgICAgaWYgdmFsX2luY2x1ZGUgPj0gdmFsX2V4Y2x1ZGU6CiAgICAgICAgICAgIG9wdFtqXSA9IHZhbF9pbmNsdWRlCiAgICAgICAgZWxzZToKICAgICAgICAgICAgb3B0W2pdID0gdmFsX2V4Y2x1ZGUKCiAgICAjIDQuIOacgOmBqeino++8iOOCuOODp+ODluOBrumbhuWQiO+8ieOCkuaxguOCgeOCiwogICAgIyDjgrnjg6njgqTjg4njga7jgqLjg6vjgrTjg6rjgrrjg6DjgavlvpPjgYTjgIHlvozjgo3jgYvjgonpgaHjgosKICAgIHNvbHV0aW9uID0gW10KICAgIGN1cnIgPSBuCiAgICB3aGlsZSBjdXJyID4gMDoKICAgICAgICAjIOOAjOOBneOBruOCuOODp+ODluOCkumBuOOCk+OBoOWgtOWQiOOAjeOBruWApOOBjOOAgeePvuWcqOOBrk9QVOWApOOBqOetieOBl+OBhOOBi+ODgeOCp+ODg+OCrwogICAgICAgICMg5ZCM54K544Gu5aC05ZCI44Gv54++5Zyo44Gu44K444On44OW44KS6YG444G277yI5p2h5Lu2OiA+PSDvvIkKICAgICAgICBpZiBzb3J0ZWRfam9ic1tjdXJyXVsndiddICsgb3B0W3BbY3Vycl1dID49IG9wdFtjdXJyLTFdOgogICAgICAgICAgICBzb2x1dGlvbi5hcHBlbmQoY3VycikKICAgICAgICAgICAgY3VyciA9IHBbY3Vycl0gIyDnm7TliY3jga7pnZ7nq7blkIjjgrjjg6fjg5bjgbjjgrjjg6Pjg7Pjg5cKICAgICAgICBlbHNlOgogICAgICAgICAgICBjdXJyIC09IDEgIyDkuIDjgaTliY3jga7jgrjjg6fjg5bjgbjnp7vli5UKCiAgICAjIOWHuuWKm+S+izEsIDIsIDMg44Gu5b2i5byP44Gr5ZCI44KP44Gb44Gm44Oq44K544OI44KS44Gd44Gu44G+44G+5Ye65YqbCiAgICBwcmludChzb2x1dGlvbikKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBzb2x2ZSgp