# SANYAM MITTAL
# CE 42
# 18001003110

import sys
from sys import maxsize

input = sys.stdin.readline

def multi_input():
    return map(int, input().split())

def array_print(arr):
    print(' '.join(map(str, arr)))


def travellingSalesmanProblem(graph, s):
    vertex = []
    for i in range(V):
        if i != s:
            vertex.append(i)

    min_path = maxsize
    while True:
        current_pathweight = 0
        k = s
        for i in range(len(vertex)):
            current_pathweight += graph[k][vertex[i]]
            k = vertex[i]
        current_pathweight += graph[k][s]
        min_path = min(min_path, current_pathweight)

        if not next_permutation(vertex):
            break

    return min_path


def next_permutation(L):
    n = len(L)

    i = n - 2
    while i >= 0 and L[i] >= L[i + 1]:
        i -= 1

    if i == -1:
        return False

    j = i + 1
    while j < n and L[j] > L[i]:
        j += 1
    j -= 1

    L[i], L[j] = L[j], L[i]

    left = i + 1
    right = n - 1

    while left < right:
        L[left], L[right] = L[right], L[left]
        left += 1
        right -= 1

    return True


print("Enter total Nodes")

V = int(input())
graph = [[0 for i in range(V)] for j in range(V)]
print("Enter Total Edges")
edges = int(input())
print("node1 node2 weight")
for e in range(edges):
    n1, n2, w = multi_input()
    graph[n1][n2] = w
s = 0
print(travellingSalesmanProblem(graph, s))
