다익스트라의 악몽 (쉬움)

시간 제한: 1000 ms. 메모리 제한: 1024 MB.

모든 컴퓨터 과학자가 알아야 하는 다익스트라 알고리즘은 주어진 그래프에서 한 시작 정점으로부터 최단 경로를 구하는 기본 알고리즘이다. 이 알고리즘은 활성 정점의 집합을 유지한다. 매 반복마다 현재 거리가 가장 작은 활성 정점을 골라 처리한다. 정점을 처리할 때는 나가는 간선을 살펴본다. 간선을 이용해 인접 정점까지의 거리를 줄일 수 있으면 거리를 갱신하고, 그 인접 정점을 활성 상태로 표시한다.

모든 간선의 길이가 0 이상이면 이 알고리즘은 효율적으로 동작한다. 이 문제의 참조 구현은 그러한 그래프에서 $O(m \log n)$ 시간에 동작한다. 여기서 $m$은 간선의 수, $n$은 정점의 수이다.

간선의 길이가 음수일 수 있으면 문제가 어려워진다. 그러한 그래프에서 단순 경로 (같은 정점을 두 번 지나지 않는 경로)의 최단 경로를 구하는 문제는 NP-난해하다. 다익스트라 알고리즘의 일부 변형은 그런 그래프에서도 빨리 끝나지만, 때때로 잘못된 결과를 낸다. 참조 구현은 잘못된 결과를 내지 않으나, 조금 다른 문제를 푼다. 각 정점 $v$에 대해 시작 정점에서 $v$까지 가는 최단 워크의 길이를 구한다. 워크는 정점과 간선을 반복해서 지나도 되는 경로이다. 모든 간선의 길이가 양수이면 최단 워크는 항상 단순 경로가 된다.

시작 정점에서 어떤 정점 $v$까지의 최단 워크가 존재하지 않을 수도 있다. 모든 워크에 대해 그보다 더 짧은 워크가 존재하기 때문이다. 이런 입력에 대해 참조 구현은 끝나지 않는다.

이 문제에서 "그래프"는 항상 중복 간선과 자기 루프가 없는 방향 가중 그래프를 뜻한다. $n$과 $m$은 각각 정점의 수와 간선의 수이다. 정점은 0부터 $n-1$까지 번호가 매겨져 있다. 시작 정점은 0이다.

이 문제에서는 다익스트라 알고리즘이 종료하지만 시간 복잡도가 정점 수에 대해 지수적인 그래프가 존재함을 보이면 된다. 참조 구현에는 PROCESSED_VERTICES라는 변수가 있다. 유한한 단계 후에 구현이 종료하고, 종료 시점의 PROCESSED_VERTICES 값이 10 000 이상이 되도록 유효한 그래프 (아래에 정의됨)를 하나 만들어라.

입력으로 d.cc와 d.py 파일이 주어진다. 두 파일은 같은 동작을 하는 참조 구현으로, 각각 C++11과 Python 2로 작성되어 있다.

유효한 그래프에서는 $1 ≤ n ≤ 60$이고, 각 간선의 길이는 부호 있는 32비트 정수에 들어간다.

그래프는 $m + 2$개의 줄로 출력한다. 첫 줄에는 $n$을, 둘째 줄에는 $m$을 쓴다. 이어지는 $m$개의 줄에는 각각 간선을 나타내는 정수 세 개를 쓴다. 앞의 두 수는 간선의 양 끝점 번호 (0부터 $n-1$까지)이고, 세 번째 수는 간선의 길이이다.

출력에는 이러한 그래프가 정확히 하나만 들어 있어야 한다.