한 번 남았다

지구이는 간선의 가중치가 $1$ 또는 $-1$인 방향 그래프에 음수 사이클이 있는지 판정하려고 벨만포드 알고리즘을 다음과 같이 구현했다.

1. 모든 정점 $v$에 대하여 $d[v]$를 $0$으로 초기화한다.
2. 갱신 한 회차는 입력에 주어진 순서대로 모든 간선 $(s, e, w)$를 훑으면서 $d[e]$에 $\min(d[e],\ d[s] + w)$를 대입하는 것이다. 간선 하나를 처리할 때마다 $d$가 곧바로 바뀌고, 같은 회차의 다음 간선은 바뀐 값을 쓴다.
3. 갱신을 $N - 2$회 반복한다. 원래대로라면 $N - 1$회여야 한다.
4. 갱신을 한 회차 더 했을 때 $d$의 값이 하나라도 바뀌면 음수 사이클이 있다고 판정한다.

3번의 반복 횟수를 하나 덜 쓴 탓에, 이 코드는 음수 사이클이 없는 그래프를 보고도 있다고 답한다. 그런 그래프를 직접 만들어서 지구이의 코드가 틀렸음을 보여라.

정점 개수 $N$이 주어진다. 정점이 $N$개이고 모든 간선의 가중치가 $1$ 또는 $-1$인 방향 그래프 중에서, 음수 사이클이 없지만 위 코드가 음수 사이클이 있다고 판정하는 그래프를 하나 출력한다. 간선을 출력하는 순서가 곧 코드가 간선을 훑는 순서이므로, 순서도 답의 일부다.

조건을 만족하는 그래프는 여러 개다. 그중 간선 개수 $M$이 가장 작은 것을 출력하고, 그런 그래프가 여럿이면 출력한 간선을 순서대로 $s_1, e_1, d_1, s_2, e_2, d_2, \dots, s_M, e_M, d_M$처럼 늘어놓아 앞에서부터 수를 비교했을 때 사전순으로 가장 앞서는 것을 출력한다.

첫째 줄에 정점 개수 $N$이 주어진다. ($50 \le N \le 100$)

첫째 줄에 정점 개수 $N$과 간선 개수 $M$을 출력한다. ($0 \le M \le N \times (N - 1)$)

둘째 줄부터 $M$개의 줄에 각 간선의 시작 정점 $s$, 끝 정점 $e$, 가중치 $d$를 출력한다. ($1 \le s, e \le N$, $s \ne e$, $d = 1$ 또는 $d = -1$)

같은 $(s, e)$ 쌍을 두 번 출력하면 안 된다.