Critical Cities in a Road Network

In a transportation network connecting several cities, a city \(c\) is considered critical (or important) if, when it is removed from the network, there exist two distinct cities \(a\) and \(b\) (where \(a \neq c\) and \(b \neq c\)) such that the shortest distance between \(a\) and \(b\) increases compared to the original network, or \(a\) and \(b\) become disconnected. In other words, if \(d(a,b)\) is the shortest distance between \(a\) and \(b\) in the original network, and \(d_c(a,b)\) is the shortest distance with city \(c\) removed, then city \(c\) is important if there exists at least one pair \((a, b)\) for which

\[ d_c(a,b) > d(a,b) \quad \text{or} \quad d_c(a,b)=\infty \text{ (while } d(a,b)<\infty\text{)}. \]

You are given a road network with \(n\) cities and \(m\) bidirectional roads. Each road connects two distinct cities and has a positive length. The cities are numbered from 1 to \(n\). Your task is to identify all the important cities in the network.

Note: When a city is removed, all roads incident to that city are removed as well.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of cities and roads, respectively. \(n\) and \(m\) satisfy \(1 \le n \le 100\) and \(0 \le m \le \frac{n(n-1)}{2}\).

Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\), indicating that there is an undirected road between city \(u\) and city \(v\) with length \(w\) (\(1 \le u, v \le n,\ u \neq v,\ 1 \le w \le 10^6\)).

outputFormat

On the first line, output a single integer representing the number of important cities. On the second line, output the indices of all important cities in increasing order, separated by spaces. If there is no important city, output an empty line for the list.

sample

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

0