Description

While everyone is being tested (tortured?) in the exam room, Xiao Dai is leisurely (annoyingly) playing a game called "Initial Dream." The game tells the story of an aspiring young man named pass who travels through different times and spaces to fight the legendary demon king chinesesonic. Xiao Dai finds the game's story flow quite complex. It has many branching plots, and different branches can proceed at the same time. Therefore, the game can be described by plots and plot endpoints, and some plots can only continue after certain specific plot endpoints are reached. To experience the game's completeness, Xiao Dai decides to see all the branches — complete all tasks. But will this delay Xiao Dai's precious sleep time? So please solve this problem.

Input Format

Xiao Dai will give you a list describing the plot flow and completion conditions.

• The first line contains a number $n$, meaning there are $n$ plot endpoints in total.
• The second line contains a number $m$, meaning there are $m$ different plots.
• Each of the next $m$ lines contains three numbers, meaning that from plot endpoint $i$, you must complete a plot that takes time $k$ in order to reach plot endpoint $j$.

Output Format

You must tell Xiao Dai the minimum time needed to complete the entire game, and all possible plot endpoints that will be passed through (output in ascending order).

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

7
1 2 3 5

Hint

Constraints

For all testdata, $0<n<100$, $0<m\le 120$, $0<i\le 100$, $0<j\le 100$, $0<k\le 1000$.

Translated by ChatGPT 5