@staticmethod
def d_2():
    (n, m, *abt) = map(int, sys.stdin.read().split())
    graph = GeometryTopology.Graph()
    for (a, b, t) in zip(*([iter(abt)] * 3)):
        a -= 1
        b -= 1
        graph.add_edge(a, b, weight=t)
        graph.add_edge(b, a, weight=t)
    dist = graph.floyd_warshall()
    res = min([max(tmp.values()) for tmp in dist.values()])
    print(res)
@staticmethod
def d_2():
    (n, m, *abt) = map(int, sys.stdin.read().split())
    graph = GeometryTopology.Graph()
    for (a, b, t) in zip(*([iter(abt)] * 3)):
        a -= 1
        b -= 1
        graph.add_edge(a, b, weight=t)
        graph.add_edge(b, a, weight=t)
    dist = graph.floyd_warshall()
    res = min([max(tmp.values()) for tmp in dist.values()])
    print(res)