import sys

# 沖突檢測
def conflict(k):
    global n, graph, x, min_cost
    # 第k個節(jié)點(diǎn)，是否前面已經(jīng)走過
    if k < n and x[k] in x[:k]:
        return True
    # 回到出發(fā)節(jié)點(diǎn)
    if k == n and x[k] != x[0]:
        return True
    # 前面部分解的旅費(fèi)之和超出已經(jīng)找到的最小總旅費(fèi)
    cost = sum([graph[node1][node2] for node1, node2 in zip(x[:k], x[1:k+1])])
    if 0 < min_cost < cost:
        return True
    return False

# 旅行商問題（TSP）
def tsp(k): # 到達(dá)（解x的）第k個節(jié)點(diǎn)
    global n, graph, x, min_cost
    if k > n: # 解的長度超出，已走遍n+1個節(jié)點(diǎn) （若不回到出發(fā)節(jié)點(diǎn)，則 k==n）
        cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])])# 計算總旅費(fèi)
        if min_cost == 0 or cost < min_cost:
            min_cost = cost
    else:
        for node in graph[x[k-1]]:# 遍歷節(jié)點(diǎn)x[k-1]的鄰接節(jié)點(diǎn)（狀態(tài)空間）
            x[k] = node
            if not conflict(k):
                tsp(k+1)



if __name__ == "__main__":
    n = int(sys.stdin.readline().strip()) # 節(jié)點(diǎn)數(shù)
    m = int(sys.stdin.readline().strip())
    graph = {}
    for i in range(n):
        graph[i] = {}
    for i in range(m):
        a, b, t = map(int, sys.stdin.readline().strip().split())
        graph[a][b] = t
        graph[b][a] = t
    x = [0] * (n + 1)
    min_cost = 0
    x[0] = 0 # 出發(fā)節(jié)點(diǎn)：路徑x的第一個節(jié)點(diǎn)（隨便哪個）
    tsp(1)   # 開始處理解x中的第2個節(jié)點(diǎn)
    if min_cost == 0:
        print(-1)
    else:
        print(min_cost)