P1841 [JSOI2007] Important Cities

Students attending the JSOI winter camp recently discovered that, due to road construction on the Nanhang campus cutting off the original route to the computing center, the travel distance increased by nearly one kilometer. However, although construction in front of the cafeteria also blocked the original route to the computing center, it did not increase the distance because an alternative route of the same length could be found. In fact, the key is that the blocked point is a critical junction. A similar situation occurs in intercity transportation. If certain cities have problems, they may cause inconvenience to traffic between many other cities. Other cities do not affect the traffic between other cities. The JSOI winter camp students found this to be an interesting problem and decided to study it. They consider a city to be important if: after a city $c$ is destroyed, there exist two distinct cities $a$ and $b$ (with $a, b \ne c$) such that the shortest distance from $a$ to $b$ increases (or becomes disconnected). In this case, city $c$ is important. Given a transportation map between cities provided by the coaches, they want to find all important cities. Now please solve this problem.

The first line contains two integers $N$ and $M$: $N$ is the number of cities, and $M$ is the number of roads. The next $M$ lines each contain three integers, representing an undirected edge between two cities and the length of the road between them.

Output a single line containing several numbers in increasing order, representing the important cities. If no such city exists, output `No important cities.`.

- For $30\%$ of the testdata, $N \le 20$. - For $60\%$ of the testdata, $N \le 100$. - For $100\%$ of the testdata, $N \le 200$, $M \le \frac{N \times (N - 1)}{2}$, $0 < c \le 10000$. Here $c$ is the length of a road. There are no multiple edges or self-loops. Translated by ChatGPT 5