Trong kì nghỉ hè năm nay sherry được bố thưởng cho 1 tour du lịch quanh N đất nước tươi đẹp với nhiều thắng cảnh nổi tiếng (vì sherry rất ngoan). Tất nhiên sherry sẽ đi bằng máy bay.
Giá vé máy bay từ đất nước i đến đất nước j là Cij ( dĩ nhiên Cij có thể khác Cji ). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng sherry cũng muốn tìm cho mình 1 hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặng mọi người ( Các chuyến bay của sherry đều được đảm bảo an toàn tuyệt đối ).
Bạn hãy giúp sherry tìm 1 hành trình đi qua tất cả các nước, mỗi nước đúng 1 lần sao cho chi phí là bé nhất nhé.
Dữ liệu
Dòng 1: N (5 < N < 10)
Dòng thứ i trong N dòng tiếp theo: Gồm N số nguyên, số thứ j là Cij (0 < Cij < 10001)
Kết quả
Gồm 1 dòng duy nhất ghi chi phí bé nhất tìm được
sherry sẽ bắt đầu đi từ thành phố 3 và có hành trình đi như sau: 3-6-5-1-2-4