I implemented a simple Python code for finding a negative cycle using the Bellman-Ford algorithm. However, I encountered a few wrong answers and a lot of TLE (Time Limit Exceeded) for the problem Finding Cycle. I didn’t try too hard to check why there is TLE, but after many dry runs, I couldn’t figure out the reason for the wrong answer. Kindly help me figure out where my implementation went wrong.

def bellman_ford(n, edges):
    dist = [float('inf')] * (n + 1)
    dist[1] = 0
    prev = [-1] * (n + 1)
    
    # Standard Bellman-Ford Algorithm
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    
    # Negative Cycle Detection
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            # Negative cycle found, reconstruct the cycle
            cycle_start = v
            for _ in range(n):
                cycle_start = prev[cycle_start]
            
            # To find the actual cycle, iterate until we get back to the start
            cycle = []
            v = cycle_start
            while True:
                cycle.append(v)
                if v == cycle_start and len(cycle) > 1:
                    break
                v = prev[v]
            cycle.append(cycle_start)  # To complete the cycle
            
            return True, cycle[::-1]  # Reverse the cycle to get the correct order
    return False, None

# Input reading and function call
n, e = map(int, input().split())
edges = []
for _ in range(e):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

chk, cycle = bellman_ford(n, edges)
if chk:
    print("YES")
    print(*cycle)
else:
    print("NO")

I attempted to implement the Bellman-Ford algorithm to detect negative cycles in a Python code, referring to the problem link provided. Initially, I expected the code to correctly identify negative cycles and provide accurate results. However, upon testing, I encountered incorrect answers and frequent Time Limit Exceeded errors. Despite conducting several dry runs, I couldn’t pinpoint the exact flaw in my implementation. I hoped to receive assistance in identifying where my code went astray.