Description

一个无环的有向图被称为有向无环图

（Directed Acyclic Graph，之后简称DAG）。AOE（Activity OnEdge）网是指以边表示活动的网，如下图所示。

在上图中共有11个活动、9个事件。整个工程只有一个开始点和一个完成点，即只有一个入度为零的点（源点）和一个出度为零的点（汇点）。关键路径指从开始点到完成点的最长路径。路径的长度是边上活动耗费的时间。如上图所示，$1-2-5-7-9$是关键路径（关键路径不止一条，输出字典序最小的），权值之和为$8$。

Format

Input

输入包含多组数据，不超过10组。第1行包含节点数$n（2≤n ≤10000）$和边数$m （1≤m ≤50000）$，接下来的$m$行，包含每条边的起点$s$和终点$e$ ，权值$w （1≤s ,e ≤n ，s !=e ，1≤w≤20）$。数据保证图连通，且只有一个源点和汇点。

Output

单行输出关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，则输出字典序最小的）。

Samples

9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
8 9 4
7 9 2

18
1 2
2 5
5 7
7 9