def backtracking(grafo, origen, ciudad_actual, ciudades_restantes, costo_actual, costo_min, trayecto):
    if len(ciudades_restantes) == 0:
        trayecto.append(origen)
        ultimo_peso = grafo.obtener_arista_peso(ciudad_actual, origen)
        if costo_min[0] == 0:
            costo_min[0] = costo_actual + ultimo_peso
            #copia el trayecto
            costo_min[1] = list(trayecto)
        if costo_actual + ultimo_peso < costo_min[0]:
            costo_min[0] = costo_actual + ultimo_peso
            #copia el trayecto
            costo_min[1] = list(trayecto)
    for v in grafo.obtener_adyacentes(ciudad_actual):
        if v in ciudades_restantes:
            peso_actual = grafo.obtener_arista_peso(ciudad_actual, v)
            nuevo_costo = costo_actual + peso_actual
            if costo_min[0] == 0 or nuevo_costo <= costo_min[0]:
                ciudades_restantes.pop(ciudades_restantes.index(v))
                #copia el trayecto
                ex = list(trayecto)
                #agrega la ciudad a la que voy al trayecto
                trayecto.append(v)
                backtracking(grafo, origen, v, ciudades_restantes, nuevo_costo, costo_min, trayecto)
                #recupero la copia del trayecto sin todo lo que se agregó en las llamadas recursivas
                trayecto = ex
                ciudades_restantes.append(v)
    return trayecto

def viajante(grafo, origen):
    ciudades_restantes = []
    costo_min = []

    costo_min.append(0)
    costo_min.append([])
    for v in grafo.obtener_vertices():
        if v != origen:
            ciudades_restantes.append(v)
    backtracking(grafo, origen, origen, ciudades_restantes, 0, costo_min, [origen])
    print(costo_min[0])
    print(costo_min[1])