@staticmethod
def d():
    (n, m, *abt) = map(int, sys.stdin.read().split())
    (a, b, t) = np.array(abt).reshape(m, 3).T
    res = shortest_path(csr_matrix((t, ((a - 1), (b - 1))), (n, n)), method='FW', directed=False)
    print(res.max(axis=(- 1)).min().astype(np.int64))
@staticmethod
def d():
    (n, m, *abt) = map(int, sys.stdin.read().split())
    (a, b, t) = np.array(abt).reshape(m, 3).T
    res = shortest_path(csr_matrix((t, ((a - 1), (b - 1))), (n, n)), method='FW', directed=False)
    print(res.max(axis=(- 1)).min().astype(np.int64))