#P1476. 休息中的小呆

休息中的小呆

题目描述

当大家在考场中接受考验(折磨?)的时候,小呆正在悠闲(欠扁)地玩一个叫“最初梦想”的游戏。游戏描述的是一个叫 pass 的有志少年在不同的时空穿越对抗传说中的大魔王 chinesesonic 的故事。小呆发现这个游戏的故事流程设计得很复杂,它有着很多的分支剧情,但不同的分支剧情是可以同时进行的,因此游戏可以由剧情和剧情的结束点组成,某些剧情必须要在一些特定的剧情结束后才能继续发展。为了体验游戏的完整性,小呆决定要看到所有的分支剧情——完成所有的任务。但这样做会不会耽误小呆宝贵的睡觉时间呢?所以就请你来解决这个问题了。

输入格式

小呆会给你一个剧情流程和完成条件的列表,

其中第一行有一个数 nn,表示总共有 nn 个剧情结束点;

第二行一个数 mm,表示有 mm个不同的剧情;

下面的 mm 行中每行有三个数,表示从剧情结束点 ii 必须完成一个耗费时间为 kk 的剧情才能到达剧情结束点 jj

输出格式

你要告诉小呆完成整个游戏至少需要多少时间,以及要经过的所有可能的剧情结束点(按升序输出)。

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

7
1 2 3 5

提示

数据范围及约定

对于全部数据,0<n<1000<n<1000<m1200<m\le 1200<i1000<i\le 1000<j1000<j\le 1000<k10000<k\le 1000