전염병 역학 조사

오직 신체적 접촉만으로 감염되지만, 약간의 접촉만으로도 바로 감염이 될 수 있는 지독한 전염병이 창궐했다. 따라서 사람들은 서로 만나는것 만으로도 전염병에 걸릴 가능성이 생겼다.

질병관리본부에서는 확실하게 감염자로 판명된 사람 $1$명은 찾아냈으나 전염병이 어느 정도까지 확산되었는지 감을 잡을 수가 없었다.

다행스럽게도 질병관리본부는 누가 누구와 언제 만났는지에 대한 모든 정보를 파악했고, 다음과 같은 규칙으로 감염이 의심되는 사람을 추리기로 하였다.

1. 쉽게 생각하기 위해 감염된 사람도 감염이 의심되는 사람으로 생각한다.
2. 아직 감염이 의심되지 않는 사람이 감염이 의심되는 사람과 만났다면 감염이 의심되는 사람으로 보기 시작한다.

만남은 시간 순서에 따라 일어나기 때문에, 서로 같은 두 사람의 만남이 어떤 시간에 일어났느냐에 따라 전염병의 감염 의심 상태가 달라질 수 있다는 사실에 유의해야 한다.

만약 여러 만남이 같은 시간에 일어났다면, 최악의 경우를 대비하기 위해서 최대한 많은 사람이 감염이 의심되도록 만남의 순서를 적용한다. 이렇게 순서를 적용하면 가능한 감염 의심 결과가 정확히 하나밖에 없다.

모든 사람들을 $1$부터 $N$까지의 정수로 표현하고 감염자로 판명된 사람은 항상 $1$이라고 가정한다. 언제 어떤 사람들이 만났는지에 대한 모든 정보가 주어질 때, 감염이 의심되는 사람들의 목록을 출력하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 모든 사람들의 수를 나타내는 자연수 $N$($1 \le N \le 10^5$)과 사람들의 만남의 총 수 $M$($0 \le M \le 2\times 10^5$)이 주어진다.

다음 이어지는 $M$개의 줄 각각에는 하나의 만남을 나타내는 세 개의 정수 $x$, $y$, $t$($1 \le x, y \le N$, $x \ne y$, $1 \le t \le 10^6$)가 주어진다. 이는, 서로 다른 두 사람 $x$와 $y$가 전염병이 일어난 후 $t$초 후에 만났음을 의미한다.

출력 형식

첫째 줄에 감염이 의심되는 모든 사람들의 번호를 오름차순으로 공백을 하나 사이에 두고 출력한다.

예제 1

5 5
2 3 1
1 2 2
3 4 2
1 3 3
2 5 4

1 2 3 5

예제 2

7 10
5 6 2
2 3 1
1 3 3
4 5 1
4 5 3
4 2 6
3 2 5
3 5 6
5 1 5
4 6 5

1 2 3 4 5

예제 3

6 4
1 2 1
2 3 1
3 4 1
5 6 1

1 2 3 4

모든 만남이 시간 $1$에 이루어졌는데, 최악의 경우 감염이 $1$번 사람에게서 $2$, $3$, $4$번 사람에게까지 퍼질 수 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설