'''
严格次小生成树求解

先生成一棵最小生成树，然后枚举不在最小生成树中的边，把边加到树中，让树中形成一个环，然后把环上
最长的原来在树上的边删掉或者把环上次长的原来在树上的边删掉，剩下的还是一个生成树，枚举所有这
样的生成树，找符合严格次小生成树定义的生成树，找其中权值和最小的生成树

'''

class MergeSet:
    def __init__(self):
        self.m = {}
        self.__root_cnt = 0

    def getRoot(self, node):
        root = node
        buf = []
        while self.m[root] != root:
            buf.append(root)
            root = self.m[root]
        for node in buf:
            self.m[node] = root

        return root

    def merge(self, a, b):
        for node in [a, b]:
            if node not in self.m:
                self.m[node] = node
                self.__root_cnt += 1

        root1 = self.getRoot(a)
        root2 = self.getRoot(b)
        if root1 != root2:
            self.m[root1] = root2
            self.__root_cnt -= 1

    def isInSameSet(self, a, b):
        if a == b:
            return True

        for node in [a, b]:
            if node not in self.m:
                return False

        return self.getRoot(a) == self.getRoot(b)

    def getRootNum(self):
        return self.__root_cnt

    def getClusters(self):
        rec = {}
        for node in self.m:
            root = self.getRoot(node)
            if root not in rec:
                rec[root] = []
            rec[root].append(node)
        return [nodes for nodes in rec.values()]


# 克鲁斯卡尔算法求解最小生成树输入为边列表，每条边表示为(起点，终点，权重)
# 返回最小生成树权重总和，以及最小生成树边列表, 生成不了最小生成树返回None
def getMinSpanTreeKruscal(edges):
    if len(edges) == 0:
        return [None, None]

    edge_list = [(w, a, b) for a, b, w in edges]
    edge_list.sort()

    merge_set = MergeSet()
    span_tree = []

    node_set = set()
    for a, b, _ in edges:
        node_set.add(a)
        node_set.add(b)

    sum = 0
    for w, a, b in edge_list:
        if merge_set.isInSameSet(a, b):
            continue

        merge_set.merge(a, b)
        span_tree.append((a, b))
        sum += w

        if len(span_tree) == len(node_set) - 1:
            break

    return [sum, span_tree] if len(span_tree) == len(node_set) - 1 else [None, None]


n, m = map(int, input().split())
edges = []
all_edges = []
edge_len = [[0x7fffffff] * (n + 1) for _ in range(n + 1)]
for i in range(m):
    a, b, w = map(int, input().split())
    all_edges.append((a, b, w))
    if w < edge_len[a][b]:
        edge_len[a][b] = w
        edge_len[b][a] = w

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if edge_len[i][j] != 0x7fffffff:
            edges.append((i, j, edge_len[i][j]))

min_sum, span_tree = getMinSpanTreeKruscal(edges)
minor_max_dis = [[0] * (n + 1) for _ in range(n + 1)]

# max_dis[i][j]表示i, j两个节点之间路径上最大的边权值
max_dis = [[0] * (n + 1) for _ in range(n + 1)]

link = [[] for _ in range(n + 1)]
for a, b in span_tree:
    link[a].append(b)
    link[b].append(a)


# 求取任意两节点之间路径上边权值的最大值和次大值
def dfs(root, prev=None):
    ans = [(root, 0, 0)]

    for child in link[root]:
        if child == prev:
            continue

        ret = dfs(child, root)
        for node1, len1, minor_len1 in ans:
            for node2, len2, minor_len2 in ret:
                if edge_len[root][child] >= len2:
                    max_dis[root][node2] = edge_len[root][child]
                    minor_max_dis[root][node2] = len2
                elif edge_len[root][child] >= minor_len2:
                    max_dis[root][node2] = len2
                    minor_max_dis[root][node2] = edge_len[root][child]
                else:
                    max_dis[root][node2] = len2
                    minor_max_dis[root][node2] = minor_len2

                max_dis[node2][root] = max_dis[root][node2]
                minor_max_dis[node2][root] = minor_max_dis[root][node2]

                max_dis[node2][node1] = max(max_dis[root][node2], len1)
                max_dis[node1][node2] = max_dis[node2][node1]

                vals = set([len1, minor_len1, max_dis[node2][root], minor_max_dis[node2][root]])
                vals = list(vals)
                vals.sort()

                minor_max_dis[node2][node1] = vals[-2] if len(vals) > 1 else vals[0]
                minor_max_dis[node1][node2] = minor_max_dis[node2][node1]

        for node2, _, _ in ret:
            ans.append((node2, max_dis[node2][root], minor_max_dis[node2][root]))

    return ans


dfs(1)

edge_in_span_tree = set()
for a, b in span_tree:
    edge_in_span_tree.add((a, b))
    edge_in_span_tree.add((b, a))

# 枚举非最小生成树上的边
min_sub = 0x7fffffff
for a, b, w in all_edges:
    if (a, b) in edge_in_span_tree and w == edge_len[a][b]:
        continue

    sub = w - max_dis[a][b]
    if sub != 0:
        min_sub = min(min_sub, sub)

    sub = w - minor_max_dis[a][b]
    if sub != 0:
        min_sub = min(min_sub, sub)

if min_sub != 0x7fffffff:
    print(min_sum + min_sub)
else:
    print(min_sum)