-----Indian National Olympiad in Informatics 2014-----
Nikhil’s slogan has won the contest conducted by Drongo Airlines and he is entitled to a free ticket between any two destinations served by the airline. All cities served by Drongo Airlines can be reached from each other by some sequence of connecting flights. Nikhil is allowed to take as many connecting flights as needed, but he must take the cheapest route between his chosen destinations.
Each direct flight between two cities has a fixed price. All pairs of cities connected by direct flights have flights in both directions and the price is the same in either direction. The price for a sequence of connecting flights is the sum of the prices of the direct flights along the route.
Nikhil has information about the cost of each direct flight. He would like to maximize the value of his prize, so he would like to choose a pair of cities on the network for which the cost of the cheapest route is as high as possible.
For instance, suppose the network consists of four cities {1, 2, 3, 4}, connected as shown on the right.
In this case, Nikhil should choose to travel between 1 and 4, where the cheapest route has cost 19. You can check that for all other pairs of cities, the cheapest route has a smaller cost. For instance, notice that though the direct flight from 1 to 3 costs 24, there is a cheaper route of cost 12 from 1 to 2 to 3.

-----Input Format:-----
- Line 1 : Two space-separated integers, C and F . C is the number of cities on the network, numbered 1, 2, . . . , C. F is the number of pairs of cities connected by a direct flight
- Lines 2 to F + 1 : Each line describes one direct flight between a pair of cities and consists of three integers, x, y and p, where x and y are the two cities connected by this flight and p is the price of this
For all direct flights, $x \neq y$, and no pair of cities is connected by more than one direct flight. If there is a direct flight from x to y with price p, there is also a flight from y to x with price p and exactly one of these two will be listed.

-----Output Format-----
- The output consists of a single integer, the maximum cost among the cheapest routes between all pairs of cities across the airline’s network.

-----Test Data-----
The testdata is grouped into three subtasks. In all subtasks, 2 ≤ C ≤ 230 and 1 ≤ F ≤ 23665. In addition, each subtask has the following constraints on the inputs.
- Subtask 1 (20 marks) : F = C − 1 (that is, the airline network is a tree) and p = 1 for each direct flight.
- Subtask 2 (30 marks) : There is no constraint on the shape of the network, but for each direct flight, p = 1.
- Subtask 3 (50 marks) : There is no constraint on the shape of the network, but for each direct flight, 0 ≤ p ≤ $10^5$.

-----Sample Input-----
4 5
1 2 10
1 3 24
2 3 2
2 4 15
3 4 7

-----Sample Output-----
19

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'MAX = 999999\r\nc, f = list(map(int, input().split()))\r\nd = []\r\nfor i in range(c):\r\n    d.append([-1 for j in range(c)] )\r\n\r\nfor i in range(f):\r\n    x, y, p = list(map(int, input().split()))\r\n    d[x-1][y-1] = p\r\n    d[y-1][x-1] = p\r\n\r\nfor i in range(c):\r\n    for j in range(c):\r\n        if i == j:\r\n            d[i][j] = 0\r\n        elif d[i][j] == -1:\r\n            d[i][j] = MAX\r\n\r\nfor w in range(c):\r\n    for i in range(c):\r\n        for j in range(c):\r\n            d[i][j] = min(d[i][j], (d[i][w] + d[w][j]))\r\n\r\np = 0\r\nfor i in range(c):\r\n    for j in range(c):\r\n        p = max(d[i][j], p)\r\n\r\nprint(p)\r\n\r\n\r\n\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13645