import sys

def evaluate(city):
    global data, distance
    for dd in data[city]:
        if distance[dd[0]] > (distance[city]+dd[1]) :
            distance[dd[0]] = distance[city]+dd[1]
            evaluate(dd[0])

data = dict()
distance = []
R = raw_input
I = input
c = I()
for i in range(c):
    [n, m] = [int(r) for r in R().split()]
    distance = [sys.maxint] * n
    distance[0] = 0
    for j in range(m):
        [a,b,cost] = [int(r) for r in R().split()]
        if a not in data:
            data[a] = []
        data[a].append([b, cost])
        if b not in data:
            data[b] = []
        data[b].append([a, cost])

    evaluate(0)
    print distance[n-1]