from itertools import permutations

N, M = map(int, input().split())

length = {}
history = []

for _ in range(M):
    a, b, c = map(int, input().split())
    length[str(min(a, b)) + str(max(a, b))] = c

for i in range(1, N):
    for j in range(i+1, N+1):
        dic = {}
        if str(i) + str(j) in length:
            dic[str(i) + str(j)] = length[str(i) + str(j)]

        array1 = [k for k in range(1, N+1)]
        array1.remove(i)
        array1.remove(j)

        for k in range(1, len(array1)+1):
            array2 = list(permutations(array1, k))
            for l in array2:
                case = ''
                for m in l:
                    case += str(m)
                case = str(i) + case + str(j)
                num = 0
                flag = True
                for m in range(len(case)-1):
                    x = str(min(int(case[m]), int(case[m+1]))) + str(max(int(case[m]), int(case[m+1])))
                    if x in length:
                        num += length[x]
                    else:
                        flag = False
                        break

                if flag:
                    dic[case] = num

        min_case = min(dic, key=dic.get)
        for k in range(len(min_case)-1):
            x = str(min(int(min_case[k]), int(min_case[k+1]))) + str(max(int(min_case[k]), int(min_case[k+1])))
            if x not in history:
                history.append(x)

print(M - len(history))
