405132: GYM101804 E Efficient Tracking

The student Navarro was called to be the company commander. As company commander, he is responsible for tracking where each member of the company is.

As there are many people, he decide to split the company in several layers and each person in the layer $$$i$$$ has his/her location tracked by someone in the layer $$$i-1$$$. Navarro is the only person in the layer $$$0$$$.

When he was splitting the people, he notice that each pair of cadets has a friendship level and the job is done better when the sum of the friendship levels between each person and the responsible for tracking his/her location is bigger.

Since he is very busy doing upsolvings of the contests and homeworks, he asked you to code a program for him that calculates the maximum friendship level possible for the whole company and tell, for each person, which other person will track down his/her location in this configuration.

The friendship level of a company configuration is defined as the sum of all friendship levels between each person and the responsible for tracking his/her location.

The first line of input contains one number $$$n$$$ ($$$2 \leq n \leq 10^3$$$) - the number of people in the company.

The next $$$n-1$$$ lines contains the friendship levels. The $$$i$$$-th line contains $$$i$$$ integers, $$$f_{ij}$$$ ($$$0 \leq f_{ij} \leq 10^5$$$) — the $$$j$$$-th integer is the friendship level between $$$(i+1)$$$-th person and $$$j$$$-th person.

You can assume that the friendship level is reciprocal. In other words, the friendship level between $$$i$$$-th person and $$$j$$$-th person is the same as the friendship level between $$$j$$$-th person and $$$i$$$-th person.

Navarro is always the person number 1 and is the only person that is not tracked down by the others.

Print the maximum friendship level of the company followed by $$$n-1$$$ lines. On $$$i$$$-th line you should print the responsible for tracking the location of the $$$(i+1)$$$-th person.

If there are multiple answers, print any of them.

3
1
2 3

5
3
1

3
2
3 1

5
1
1

4
3
4 5
3 2 1

12
3
1
1