#! /usr/bin/python

import numpy
import sys

matriz = numpy.zeros((4+1,4+1)) # cria uma matriz de tamanho n+1 x peso+1 de zeros

N = 4
caminho = []

matriz[0][0] = 999
matriz[0][1] = 999
matriz[0][2] = 999
matriz[0][3] = 999
matriz[0][4] = 999

matriz[1][0] = 999
matriz[1][1] = 999
matriz[1][2] = 23
matriz[1][3] = 17
matriz[1][4] = 19

matriz[2][0] = 999
matriz[2][1] = 14
matriz[2][2] = 999
matriz[2][3] = 22
matriz[2][4] = 20

matriz[3][0] = 999
matriz[3][1] = 23
matriz[3][2] = 15
matriz[3][3] = 999
matriz[3][4] = 25

matriz[4][0] = 999
matriz[4][1] = 13
matriz[4][2] = 19
matriz[4][3] = 21
matriz[4][4] = 999



print matriz
coluna_principal = 0
linha1 = 1

caminho.append(1)

def procurar_lista(lista,num):
    for n in xrange(len(caminho)):
        if (caminho[n] == num):
            return 1
        else:
            return 0


def testar(lista):


for linha in xrange(N):
    #print linha+1
    menor = min(matriz[linha+1])
    #print menor
    for coluna in xrange(N):
        coluna_principal = coluna+1

        #print coluna+1

        excluido = procurar_lista(caminho,coluna_principal)
        if(matriz[linha1][coluna+1] == menor and excluido != 1):

            linha1 = coluna_principal
            #print matriz[linha1][coluna+1]
            #print linha1
            #excluido = procurar_lista(caminho,linha1)
            #if(excluido != 1):
            print coluna_principal
            caminho.append(coluna_principal)
            #print caminho

            #print coluna+1

    #print "\n"
print matriz
caminho.append(1)

print caminho