题目描述

给定一个AOE网，求出它的关键路径。

AOE网：在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图为用边表示活动的网络，简称AOE网（Activity On Edge Network）。


事件的最早发生时间ve[k]：ve[k]是指从始点开始到顶点vk的最大路径长度。ve[k]=max{ve[j]+lenj,vk>}。lenj,vk>表示该边的权值。当k为1时，ve[1]=0。 


事件的最迟发生时间vl[k]：vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。vl[k]=min{vl[j]-lenk,vj>}。vl[j]-lenk,vj>表示该边的权值。当k为n时，vl[n]=ve[n]。 


关键路径：在AOE网中，从源点（入度为0的点）到汇点（出度为0的点）最长的路径称为关键路径。关键路径所经过的事件必为关键事件，即ve[i]=vl[i]（事件的最早发生时间和最迟发生时间一致）。

输入格式

第一行共有两个整数，n和m，代表顶点数和边数。

接下来m行，每行有三个整数，a,b,c 代表一条边，由顶点a指向顶点b，权值为c。 


保证顶点1的入度为0，顶点n的出度为0。

输出格式

输出该AOE网中所有的关键路径。

每行为一条关键路径。


若有多条关键路径，则按顶点数字小的在前。 


如：


1->2->3->4->7->9 


1->2->5->7->9 


1->2->5->8->9


1->3->4->7->9

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

1->3->4->6->8

提示

红色路径即为关键路径。