mx = (1 << 33) - 1

n = int(input())

grf = [[0 for j in range(n)] for i in range(n)]

st = input()
while(st != ""):
    i, j, val = map(int, st.split())
    grf[i - 1][j - 1] = val
    st = input()

mkr = list(map(list, grf))

flag = True
while(flag):
    flag = False

    for i in range(n):
        for j in range(n):
            if(i == j):
                continue

            for k in range(n):
                if(k != i and k != j and (mkr[i][j] > grf[i][k] + grf[k][j] or mkr[i][j] == 0) and grf[i][k] != 0 and grf[k][j] != 0):
                    flag = True
                    mkr[i][j] = grf[i][k] + grf[k][j]

for ip in range(n):
        for jp in range(n):
            if(ip == ip):
                break

            i, p = ip, jp
            print(str(i) + "->" + str(j) + "(" + str(mkr[i][j]) + "):")
            print(str(i) + "->", end = '')
            while(grf[i][j] != mkr[i][j]):
                for k in range(n):
                    if(k != i and k != j and mkr[i][k] and grf[i][j] == mkr[i][k] + mkr[k][j]):
                        print(str(k) + "(" + str(mkr[i][k]) + ")->", end = '')
                        i = k
                        break

            print(str(j) + "(" + str(mkr[i][j]) + ")")