Here is the solution:
dist := [0] * (n + 1)
parent := [-1] * (n + 1)
for round from 1 to n - 1
for (u, v, w) in edges
if dist[u] + w < dist[v] then
dist[v] := dist[u] + w
parent[v] := u
// Find node in cycle
cycle_node := -1
for (u, v, w) in edges
if dist[u] + w < dist[v] then
cycle_node := v
break
// Trace back to find cycle
if cycle_node != -1 then
for i from 1 to n
cycle_node := parent[cycle_node]
// Now trace the cycle
current := cycle_node
cycle := []
repeat
cycle.append(current)
current := parent[current]
until current = cycle_node
cycle.reverse()
print cycle
The double-walk guarantees correct cycle extraction even when the improved node is outside the cycle.
This runs in time and uses space.