题目描述

给定一个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]。 


活动的最早开始时间e[i]：若活动ai是由边vk , vj>表示,则e[i]=ve[k]。 


活动的最晚开始时间l[i]：若活动ai是由边vk , vj>表示,则l[i]=vl[j]-lenk,vj>。

输入格式

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

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


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

输出格式

输出共四行，前两行每行n个数，后两行每行m个数。即输出ve，vl, e  , l  这四个数组。

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
7 9 2
8 9 4

0 6 4 5 7 7 16 14 18
0 6 6 8 7 10 16 14 18
0 0 0 6 4 5 7 7 7 16 14
0 2 3 6 6 8 7 7 10 16 14

提示