# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")
from collections import *
from functools import *
from itertools import *
from heapq import *
import sys, math
# sys.setrecursionlimit(10**4)
input = sys.stdin.readline
INF = (1<<60)
def dijkstra(s,e):
    
    N = len(e)
    dist = [INF]*N
    dist[s]=0
    h = []
    bef = [-1]*N
    heappush(h,s)
    while h:
        nw,v = divmod(heappop(h),N)
        if dist[v]!=nw:
            continue
        for iv,ic in e[v]:
            nc = ic + nw
            if nc < dist[iv]:
                bef[iv] = v
                dist[iv] = nc
                heappush(h,nc*N + iv)
    return dist,bef
def answer1():
    N,M = map(int,input().split())
    e = [[] for _ in range(N)]
    for _ in range(M):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        e[u].append((v,w))
    ans = INF
    d = [dijkstra(s,e)[0] for s in range(N)]
    for i in range(N-1):
        for j in range(i+1,N):
            ans = min(ans,d[i][j] + d[j][i])
    if ans==INF:
        print(-1)
    else:
        print(ans)
    return

def answer0():
    N,M = map(int,input().split())
    e = [[] for _ in range(N)]
    for _ in range(M):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        e[u].append((v,w))
        e[v].append((u,w))

    ans = INF
    for r in range(N):
        dist,bef = dijkstra(r,e)

        for i in range(N):
            for j,wj in e[i]:

                if (bef[i]!=j)&(bef[j]!=i):
                    ans = min(ans,dist[i]+dist[j]+wj)
    if ans==INF:
        print(-1)
    else:
        print(ans)
T = int(input())
if T==1:
    answer1()
else:
    answer0()