Lộ trình rẻ nhất

Một nhà thám hiểm muốn ghé thăm đủ \(N\) thành phố, được đánh số từ \(1\) đến \(N\), bằng đường hàng không. Anh ta được tự do chọn thành phố xuất phát, sau đó bay lần lượt qua các thành phố còn lại sao cho mỗi thành phố được ghé đúng một lần (không cần quay về điểm đầu).

Giá vé bay thẳng từ thành phố \(i\) đến thành phố \(j\) là \(c_{i,j}\) (giá vé chiều đi và chiều về có thể khác nhau). Trong bài này, hãy chỉ ra một hành trình có tổng tiền vé nhỏ nhất.

Nếu có nhiều hành trình cùng có tổng tiền vé nhỏ nhất, hãy in hành trình có thứ tự từ điển nhỏ nhất (so sánh dãy các thành phố theo thứ tự ghé thăm, tại vị trí đầu tiên khác nhau, dãy có số nhỏ hơn được coi là nhỏ hơn).

Input

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(N\) số nguyên \(c_{i,1}, c_{i,2}, \dots, c_{i,N}\).

Output

In ra \(N\) số nguyên trên một dòng, cách nhau một dấu cách: các thành phố theo thứ tự được ghé thăm.

Constraints

• \(1 \le N \le 16\).
• \(c_{i,i} = 0\); với \(i \ne j\) thì \(1 \le c_{i,j} \le 10^9\).

Sample Input

5
0 2 9 4 6
3 0 1 7 2
8 5 0 3 1
2 6 4 0 5
7 1 3 2 0

Sample Output

1 2 3 5 4

Explanation

Hành trình \(1 \to 2 \to 3 \to 5 \to 4\) có tổng chi phí \(2 + 1 + 1 + 2 = 6\), đây là mức nhỏ nhất và là hành trình nhỏ nhất theo thứ tự từ điển trong các hành trình tối ưu.