题目描述
一个无环的有向图被称为有向无环图（Directed Acyclic Graph，之后简称DAG）。AOE（Activity On Edge）网是指以边表示活动的网，如下图所示。
在上图中共有11个活动、9个事件。整个工程只有一个开始点和一个完成点，即只有一个入度为零的点（源点）和一个出度为零的点（汇点）。关键路径指从开始点到完成点的最长路径。路径的长度是边上活动耗费的时间。如上图所示，1-2-5-7-9是关键路径（关键路径不止一条，输出字典序最小的），权值之和为18。
在上图中共有11个活动、9个事件。整个工程只有一个开始点和一个完成点，即只有一个入度为零的点（源点）和一个出度为零的点（汇点）。关键路径指从开始点到完成点的最长路径。路径的长度是边上活动耗费的时间。如上图所示，1-2-5-7-9是关键路径（关键路径不止一条，输出字典序最小的），权值之和为18。
输入
输入包含多组数据，不超过10组。第1行包含节点数n（2≤n ≤10000）和边数m （1≤m ≤50000），接下来的m 行，包含每条边的起点s 和终点e ，权值w （1≤s ,e ≤n ，s !=e ，1≤w≤20）。数据保证图连通，且只有一个源点和汇点。
输出
单行输出关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，则输出字典序最小的）。
样例输入 Copy
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
样例输出 Copy
18
1 2
2 5
5 7
7 9