ルパン四世

怪盗「ルパン四世」は会津藩士を末裔とする美女「富士峰子」より、会津若松市に会津藩が残した軍資金が眠っていることを聞かされる。ルパンの長年の仲間である「石川越ェ門」の報告によれば、軍資金は千両箱に収められいくつかの蔵に保管されている。蔵に見張りはいないが厳重に施錠されている。しかし、越ェ門は彼が父から伝授された秘伝「鋼鉄斬り」の技を繰り出せば瞬時に蔵を破れるという。

残った問題は千両箱の運搬だ。体力のないルパンと越ェ門は千両箱を一つも持てない。そこで、頼りになる男「無限大介」に運搬を頼んだ。 すべての千両箱を運び出すために、ルパンは以下のような計画を立案した。

まず、ルパンの運転で最初の蔵へ行き、越ェ門と大介を降ろす。

• 越ェ門が蔵を破る
• 大介がすべての千両箱を運び出す
• その千両箱を持ったままルパンが決めた次の蔵へ向かう

これを繰り返し、最後の蔵まで破り千両箱を運び出す。その間にルパンはヘリコプターを準備し最後の蔵で二人と千両箱を運び上げ脱出する。大介はどんなに重いものも運搬できるが、荷物の重さに応じて移動速度は遅くなる。ルパンは、このことを考慮して蔵を破る順番を決めなければならない。

ルパンに代わって、最初の蔵を破ってから最後の蔵に辿りつくまでの移動時間が最小となるような蔵を破る順番を出力するプログラムを作成してください。ただし、

• 蔵はすべて鶴ヶ城からまっすぐ北に走る通りに面している。蔵の数は高々 15 個であり、城からの距離は高々 10000 メートル以下である。
• 千両箱の重さはいずれもひとつ 20 キログラムである。それぞれの蔵に収められている千両箱の個数は 10000 個以下である。
• 蔵から蔵への移動は、通りに沿って地下に設置されている地下道を使う。
• 大介は w キログラムの荷物を運ぶのに、分速 2,000／(70 + w) メートルで移動する。

入力データは、それぞれの蔵について蔵の番号（100 以下の整数）と城からの距離（メートル）とその蔵に保管されている千両箱の個数が与えられる。

Input

入力は以下の形式で与えられます。

n
s1 d1 v1
s2 d2 v2
:
sn dn vn

1 行目に蔵の個数 n（n ≤ 15）、続く n 行に第 i の蔵の情報が与えられます。蔵の情報として、蔵の番号 s_i (1 ≤ s_i ≤ 100)、城からの距離 d_i (1 ≤ d_i ≤ 10000)、 千両箱の数 v_i (1 ≤ v_i ≤ 10000) が１行に与えられます。

Output

蔵を破る順番を１行に出力してください。蔵の番号を空白で区切ってください。

Sample Input 1

2
1 100 1
2 200 2

Output for the Sample Input 1

1 2

Sample Input 2

3
11 100 1
13 200 20
12 300 3

Output for the Sample Input 2

11 12 13

Sample Input 3

5
13 199 1
51 1000 1
37 350 10
27 300 2
99 200 1000

Output for the Sample Input 3

51 37 27 13 99