题目描述

\(X\) 建筑公司承接了某市扩建工程，经过前期的规划和设计 \(X\) 公司将工程分成了许多子工程，并分别承包给了各个承包商。\(X\) 公司为了方便管理，将整个工程以图的形式呈现了出来，图中的有向边表示一个子工程，边权表示该子工程施工所需的时间，结点表示事件，结点的入边和出边，表示所有出边开始施工的前提条件是所有入边已经施工完成。

\(X\) 公司的总裁想知道完成整个工程所需的最短时间，及关键子工程。

关键子工程是指，在满足整个工程在最短时间完成的条件下，那些前提条件一旦满足必须立刻开始施工，且必须在规定时间内完成的子工程。

现在给你 \(N\) 个点，\(M\) 条有向边，请你输出完成整个工程的最短时间，及所有表示关键子工程的有向边 \(<u_i,v_i>\)。\(u_i\) 小的在前，\(u_i\)相同的 \(v_i\) 小的在前。

格式

输入格式

第一行两个正整数 \(N\) 和 \(M\)；

以下 \(M\) 行，每行三个正整数 \(u,v,w\)，表示有一条 \(u\) 到 \(v\) 的有向边，边权为 \(w\)。

输出格式

第一行输出一个整数，表示完成整个工程所需的最短时间；

以下每行输出一条边 \(u,v\)，表示关键子工程。

样例1

样例输入1

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

样例输出1

18
1 7
5 3
6 3
7 5
7 6
8 1

限制

时间：\(1s\) 空间：\(256M\)

对于 \(100\%\) 的数据：\(5≤N≤10^5，N-1≤M≤10^6\)；

数据保证是有向无环图，但入度和出度为 \(0\) 的点不保证唯一。

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)
模拟赛\(T2\)