Absolute Connectivity in Villages

In Gensokyo, the teacher Ueshiba Keine is famous for her extensive knowledge. Due to an unusual snowfall anomaly, many roads in the Human Village are blocked by heavy snow, preventing some students from reaching Keine's village. Therefore, she decides to relocate her classes to a village that can gather the maximum number of students.

The Human Village consists of $N$ villages (numbered from $1$ to $N$) and $M$ roads. Each road is of one of two types: type $1$ indicates a one‐way road, and type $2$ indicates a two‐way (bidirectional) road. If there exists a route from village $A$ to village $B$, we denote it as $(A,B)$. If both $(A,B)$ and $(B,A)$ hold, then villages $A$ and $B$ are said to be absolutely connected, denoted as $\langle A,B\rangle$. An absolute connectivity region is defined as a set of villages in which every pair of villages $X$ and $Y$ satisfies $\langle X,Y\rangle$.

Your task is to find the largest absolute connectivity region and output its village numbers in increasing order. If there are multiple regions of maximum size, output the lexicographically smallest one (e.g. between regions {1,3,4} and {2,5,6}, output {1,3,4}).

inputFormat

The first line contains two integers $N$ and $M$, where $N$ is the number of villages and $M$ is the number of roads. Each of the following $M$ lines contains three integers $U$, $V$, and $T$, where $U$ and $V$ denote village numbers and $T$ denotes the road type ($1$ for one‐way and $2$ for two‐way).

outputFormat

Output the village numbers in the largest absolute connectivity region in increasing order, separated by spaces. In case of a tie (multiple regions with maximum size), output the lexicographically smallest sequence.

sample

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

1 2