#当时没有考虑n==1的情况，以及判断没有路径的情况， 只有63%
#不知道现在加上能不能ac
def dfs(res,num,fg,i,cnt):
    if sum(fg) == 2 and fg[0] == 1 and  num[i][0] != -1:  #只剩两个城市 ,起点还未到达, 且可以返回起点
        res.append(cnt+num[i][0])
        return 
    if fg[0] == 0:      #无法回到起点，起点被遍历两遍
        return
    for kk in range(n):
        if num[i][kk] != -1 and fg[kk] > 0: #有路且去向城市未访问过
            fg[i] -= 1
            dfs(res,num,fg,kk,cnt+num[i][kk])  #
            fg[i] += 1
    return
 
n = int(input())
if n ==1:        #考虑n==1的情况
    print(0)
else:
    m = int(input())
    num =[[ -1 for i in range(n)] for j in range(n)]

    for k in range(m):  #构造邻接矩阵
        i,j,d = [int(tmp) for tmp in input().split(' ')]
        num[i][j] = d
        num[j][i] = d

    fg = [1]*n         #改点是否访问标志
    fg[0] = 2     #起点需访问两遍
    res = []
    dfs(res,num,fg,0,0)

    if len(res) == 0: #考虑没有路径的情况
        print(-1)
    else:
        print(min(res))