일단 저는 아래와 같이 생각하고 코드를 짰습니다.

벨만 포드 알고리즘을 사용했습니다. 

N번째 반복에서 갱신되는 노드들을 따로 표시해줬고, 양의 사이클에 포함되는 노드들을 거쳐서 가는 경로들은 답이 될 수 없게 했습니다. 

dfs로 경로를 구했을 때 N에 도달하지 못했다면 -1을 출력합니다. 

어떤게 틀렸을까요.. 답답합니다.