def make_graph(arr, n):
    # Создает словарь перекрестков:
    # {перекресток: {связанный перекресток: шанс выжить, ...}}
    graph = {i: {} for i in range(1, n+1)}
    for i in arr:
        graph[i[0]][i[1]] = i[2]
        graph[i[1]][i[0]] = i[2]
    return graph


def route(arr, n):
    g = make_graph(arr, n)
    pos = 1  # Текущая позиция.
    way = [1]  # Пройденный путь.
    surv = 100  # Шанс выжить.
    surv_hist = [100]  # Шансы выживания на каждом шаге.
    while pos != n:
        m = max(g[pos].values())
        new_p = list(g[pos].keys())[list(g[pos].values()).index(m)]
        surv = surv * m / 100
        g[pos][new_p] = 0
        # Шанс выживания для улицы обнуляется, чтобы мышь не бегала кругами
        if new_p in way:
            # Если мышь вернулась на перекресток, на котором уже была,
            # весь пройденный путь, после первого посещения этого перекрестка
            # удаляется.
            del way[(way.index(new_p))+1:]
            del surv_hist[(way.index(new_p))+1:]
            surv = surv_hist[-1]
        else:
            pos = new_p
            way.append(pos)
            surv_hist.append(round(surv, 2))
    return ' - '.join(str(i) for i in way), round(surv, 2)


N = 4
RoadOfDeathArr = ((1, 2, 98), (1, 3, 50), (1, 4, 20), (2, 4, 99), (3, 4, 70))

way, ch = route(RoadOfDeathArr, N)
print('Безопасный маршрут: ' + way)
print('Вероятость спасения на маршруте: ' + str(ch))