[SWEA] 최소 이동 거리

T = int(input())
for TC in range(T):
    N, E = map(int, input().split())
    check = [999999]*(N+1)
    arr = [[0]*(N+1) for _ in range(N+1)]
    check[0] = 0   # 출발점은 항상 0

    for i in range(E):   # E만큼 입력받기
        s, e, w = map(int, input().split())
        arr[s][e] = w    # 2차원 리스트 사용, w비용 넣기

    for i in range(N+1):
        for j in range(N+1):
            if arr[i][j] != 0:   # 경로가 있다면
                if check[j] > arr[i][j] + check[i]:   # 지금 경로가 다음 경로에 저장된 값보다 작다면
                    check[j] = arr[i][j] + check[i]   # 갱신

    print('#{} {}'.format(TC+1, check[N]))