def minimize_maximum_edge_weight_brute_force(number_of_locations, roads):

    # Sort the edges by weight to make the guessing process easier.
    roads.sort(key=lambda road: road[2])

    for maximum_allowed_weight in range(1, 101): # Iterate through possible weights
        accessible_roads = []
        for start_location, end_location, road_weight in roads:
            if road_weight <= maximum_allowed_weight:
                accessible_roads.append((start_location, end_location))

        # Check if all locations are connected with the current weight limit.
        if is_graph_connected(number_of_locations, accessible_roads):
            return maximum_allowed_weight

def is_graph_connected(number_of_locations, accessible_roads):
    if number_of_locations == 0:
        return True
    if not accessible_roads and number_of_locations > 1:
        return False

    visited_locations = set()
    queue = [1] # Start BFS from location 1
    visited_locations.add(1)

    while queue:
        current_location = queue.pop(0)

        for start_location, end_location in accessible_roads:
            if start_location == current_location and end_location not in visited_locations:
                queue.append(end_location)
                visited_locations.add(end_location)
            elif end_location == current_location and start_location not in visited_locations:
                queue.append(start_location)
                visited_locations.add(start_location)

    # Ensure every location was visited.
    return len(visited_locations) == number_of_locations

def minimize_maximum_edge_weight(number_of_nodes, edges):
    left = 0
    right = max(edge[2] for edge in edges)
    minimum_maximum_weight = right

    while left <= right:
        mid = (left + right) // 2

        # Check if the graph is connected with the current maximum weight.
        if is_connected(number_of_nodes, edges, mid):
            minimum_maximum_weight = mid
            right = mid - 1
        else:
            left = mid + 1

    return minimum_maximum_weight

def is_connected(number_of_nodes, edges, max_weight):
    adj = [[] for _ in range(number_of_nodes)]
    for source, destination, weight in edges:
        if weight <= max_weight:
            adj[source - 1].append(destination - 1)
            adj[destination - 1].append(source - 1)

    visited = [False] * number_of_nodes

    # Start DFS from node 0
    dfs(0, adj, visited)

    #If all nodes were visited, the graph is connected
    return all(visited)

def dfs(node, adj, visited):
    visited[node] = True
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs(neighbor, adj, visited)

# Example usage (This part is NOT part of the solution, just for testing)
if __name__ == '__main__':
    number_of_nodes = 4
    edges = [[1, 2, 3], [2, 3, 5], [3, 4, 7], [1, 4, 9]]
    result = minimize_maximum_edge_weight(number_of_nodes, edges)
    print(f"Minimum maximum edge weight: {result}")