다익스트라의 악몽 (어려움)

모든 컴퓨터 과학자는 다익스트라 알고리즘에 익숙해야 합니다. 이 알고리즘은 주어진 그래프에서 한 시작점으로부터의 최단 거리를 구하는 기본 알고리즘입니다. 알고리즘을 실행하는 동안 "활성" 정점들의 집합을 관리합니다. 각 반복에서 현재 거리가 가장 작은 활성 정점을 골라 처리합니다. 정점을 처리할 때는 나가는 간선을 검사합니다. 간선 하나로 인접 정점까지의 거리를 줄일 수 있으면 거리를 갱신하고, 그 인접 정점을 활성으로 표시합니다.

모든 간선의 길이가 0 이상이면 이 알고리즘이 효율적으로 동작한다는 것은 잘 알려져 있습니다. 이 문제에서 제공하는 참조 구현은 그런 그래프에 대해 $O(m\log n)$ 시간에 동작합니다. 여기서 $m$은 간선의 수, $n$은 정점의 수입니다.

간선의 길이가 음수일 수 있으면 상황이 복잡해집니다. 그런 그래프에서 최단 단순 경로(같은 정점을 두 번 지나지 않는 경로)를 찾는 문제는 NP-hard입니다. 다익스트라 알고리즘의 일부 변형은 그런 그래프에서도 빨리 끝나지만, 때로는 잘못된 결과를 냅니다. 참조 구현은 이런 문제가 없습니다. 참조 구현은 실제로 약간 다른 문제를 풉니다. 각 정점 $v$에 대해, 시작 정점에서 $v$까지 가는 워크(정점과 간선이 반복되어도 되는 경로) 중 가장 짧은 것의 길이를 구합니다. (모든 간선의 길이가 양수이면 최단 워크는 반드시 단순 경로가 됩니다.)

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

이 문제에서 "그래프"는 항상 중복 간선과 자기 루프가 없는 방향 가중 그래프를 뜻합니다. 문자 $n$과 $m$은 각각 정점 수와 간선 수를 나타냅니다. 정점은 0부터 $n - 1$까지 번호가 붙어 있습니다. 시작 정점은 0입니다.

다익스트라 알고리즘이 유한한 시간에 끝나지만, 계산 시간이 정점 수에 대해 지수적인 그래프가 존재함을 보이십시오.

참조 구현에는 PROCESSED_VERTICES라는 변수가 있습니다. 여러 개의 값 $p$가 주어집니다. 각 $p$에 대해, 참조 구현이 유한 번의 단계 후에 끝나고, 끝났을 때 PROCESSED_VERTICES의 값이 정확히 $p$가 되는 유효한 그래프를 하나 구성하십시오.

파일 d2.in이 주어집니다. 이 파일의 첫 줄에는 테스트 케이스의 개수 $t$가 적혀 있습니다. 각 테스트 케이스 앞에는 빈 줄이 있습니다. 각 테스트 케이스는 정수 $p$가 적힌 한 줄로 이루어집니다. $1 \le p \le 10\,000\,000$이라고 가정해도 됩니다.

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

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

출력에는 이런 그래프를 $t$개 차례로 담으십시오. 그래프 사이에 빈 줄을 출력하지 마십시오.

이 그래프에서 구현은 정확히 6개의 정점을 처리합니다. 처리하는 순서는 0, 3, 11, 7, 11(다시), 1입니다.