There are at most \(15 \times 13 \times 11 \times 9 \times 7 \times 5 \times 3 \times 1 = 2027025\) ways to choose as many edges as possible (for either \(N = 15\) or \(16\)), so brute force works.

Sample Implementation (Python)

N = int(input())
D = [[0 for j in range(N)] for i in range(N)]
for i in range(N - 1):
    d = list(map(int, input().split()))
    for j in range(i + 1, N):
        D[i][j] = D[j][i] = d[j - i - 1]


def dfs(used):
    if all(used):
        return 0
    v = used.index(False)
    used[v] = True
    ret = 0
    for w in range(v + 1, N):
        if not used[w]:
            used[w] = True
            ret = max(ret, D[v][w] + dfs(used))
            used[w] = False
    used[v] = False
    return ret


used = [False] * N
ans = 0
if N % 2 == 0:
    ans = dfs(used)
else:
    for v in range(N):
        used[v] = True
        ans = max(ans, dfs(used))
        used[v] = False
print(ans)

P.S. I proposed A, B, and C.