from typing import List


def useless_flight(schedule: List) -> List:
    result = []
    nodes = [s for s, d, _ in schedule] + [d for s, d, _ in schedule]

    for i, e in enumerate(schedule):
        x, y, p = e
        graph = sorted([z for z in schedule if z != e], key=lambda x: x[2])

        if nodes.count(x) > 1 and nodes.count(y) > 1 and route_price(graph, x, y, [], p) < p:
            result.append(i)
    return result


def route_price(graph, source, dest, visited, best=100000, price=0):
    if source == dest:
        return price

    for s, d, p in graph:
        if d == source:
            s, d = d, s
        if s == source and d not in visited and price + p < best:
            p_new = route_price(graph, d, dest, visited + [s], best, price + p)
            best = min(best, p_new)
    return best


if __name__ == '__main__':
    print("Example:")
    print(useless_flight([['A', 'B', 50],
                          ['B', 'C', 40],
                          ['A', 'C', 100]]))

    # These "asserts" are used for self-checking and not for an auto-testing
    assert useless_flight([['A', 'B', 50],
                           ['B', 'C', 40],
                           ['A', 'C', 100]]) == [2]
    assert useless_flight([['A', 'B', 50],
                           ['B', 'C', 40],
                           ['A', 'C', 90]]) == []
    assert useless_flight([['A', 'B', 50],
                           ['B', 'C', 40],
                           ['A', 'C', 40]]) == []
    assert useless_flight([['A', 'C', 10],
                           ['C', 'B', 10],
                           ['C', 'E', 10],
                           ['C', 'D', 10],
                           ['B', 'E', 25],
                           ['A', 'D', 20],
                           ['D', 'F', 50],
                           ['E', 'F', 90]]) == [4, 7]
    assert useless_flight([["A", "E", 45], ["A", "H", 85], ["A", "K", 60], ["A", "N", 20], ["B", "C", 90],
                           ["B", "Q", 70], ["B", "X", 60], ["B", "Y", 100], ["C", "R", 55], ["C", "X", 30],
                           ["D", "F", 10], ["D", "T", 50], ["D", "U", 75], ["D", "V", 35], ["E", "H", 55],
                           ["E", "J", 40], ["E", "M", 35], ["F", "J", 95], ["F", "M", 10], ["G", "N", 75],
                           ["G", "P", 75], ["G", "W", 40], ["H", "V", 15], ["I", "O", 10], ["I", "Q", 10],
                           ["I", "S", 70], ["J", "M", 80], ["J", "V", 20], ["K", "U", 85], ["K", "V", 80],
                           ["K", "Y", 35], ["L", "P", 15], ["L", "R", 40], ["L", "X", 50], ["N", "P", 70],
                           ["N", "W", 30], ["O", "Q", 40], ["O", "S", 55], ["O", "U", 45], ["P", "W", 90],
                           ["Q", "Y", 10], ["R", "X", 95], ["S", "T", 100], ["T", "U", 30], ["W", "Y", 15]]) == [7, 17, 19, 25, 26, 36, 41]