import random
 
def bestpath(l):
    n = len(l)
    best = ['{']*n
    best[0] = l[0][0]
    for i in range(1, n):
        for k in range(i+1):
            prev = min(l[i-1][k-1], l[i-1][k])
            if prev == best[i-1]:
                best[i] = min(best[i], l[i][k])
            else:
                l[i][k] = '{'
    return best
 
l = []
n = 5
for i in range(1,n+1):
    l.append([chr(97  + random.randint(0,5)) for _ in range(i)])
    l[-1].append('{')
    print(''.join(l[-1][:-1]))
 
print('--------')
print(''.join(bestpath(l)))

aW1wb3J0IHJhbmRvbQoKZGVmIGJlc3RwYXRoKGwpOgogICAgbiA9IGxlbihsKQogICAgYmVzdCA9IFsneyddKm4KICAgIGJlc3RbMF0gPSBsWzBdWzBdCiAgICBmb3IgaSBpbiByYW5nZSgxLCBuKToKICAgICAgICBmb3IgayBpbiByYW5nZShpKzEpOgogICAgICAgICAgICBwcmV2ID0gbWluKGxbaS0xXVtrLTFdLCBsW2ktMV1ba10pCiAgICAgICAgICAgIGlmIHByZXYgPT0gYmVzdFtpLTFdOgogICAgICAgICAgICAgICAgYmVzdFtpXSA9IG1pbihiZXN0W2ldLCBsW2ldW2tdKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgbFtpXVtrXSA9ICd7JwogICAgcmV0dXJuIGJlc3QKICAgIApsID0gW10KbiA9IDUKZm9yIGkgaW4gcmFuZ2UoMSxuKzEpOgogICAgbC5hcHBlbmQoW2Nocig5NyAgKyByYW5kb20ucmFuZGludCgwLDUpKSBmb3IgXyBpbiByYW5nZShpKV0pCiAgICBsWy0xXS5hcHBlbmQoJ3snKQogICAgcHJpbnQoJycuam9pbihsWy0xXVs6LTFdKSkKCnByaW50KCctLS0tLS0tLScpCnByaW50KCcnLmpvaW4oYmVzdHBhdGgobCkpKQ==