from collections import defaultdict, namedtuple

def connect(graph, u, v, w):
    graph[u][v] = w
    graph[v][u] = w

def tsp(d):
    """solve the traveling salesman problem by bitDP
    Parameters
    -----------
    d : list of list or numpy.array
        distance matrix; d[i][j] is the distance between i and j
    Returns
    -------
    the minimum cost of TSP
    """
    n = len(d)  # number of cities

    # DP[A] = {v: value}
    #   A is the set of visited cities other than v
    #   v is the last visited city
    #   value is the cost
    DP = defaultdict(dict)

    for A in range(1, 1 << n):
        if A & 1 << 0 == 0: # 0 is not included in set A
            continue

        # main
        for v in range(n):
            if A & (1 << v) == 0:  # v is not included in set A
                if A == (1 << 0):  # v is the first visited city
                    DP[A][v] = d[0][v] if d[0][v] > 0 else float('inf')
                else:
                    # A ^ (1 << u) <=> A - {u}
                    DP[A][v] = float('inf')
                    for u in range(1, n):
                        if d[u][v] > 0 and A & (1 << u) != 0:
                            DP[A][v] = min(DP[A][v], DP[A ^ (1 << u)][u] + d[u][v])
    V = 1 << n
    DP[V][0] = float('inf')
    for u in range(1, n):
        if d[u][0] > 0 and A & (1 << u) != 0:
            DP[V][0] = min(DP[V][0], DP[A ^ (1 <<u)][u] + d[u][0])

    return DP[V][0]

# 入力
N, M = map(int, input().split())
graph = [[0 for i in range(N)] for j in range(N)]
for _ in range(M):
    u, v, w = map(int, input().split())
    connect(graph, u-1, v-1, w)

res = tsp(graph)
print(res)