Nancy的男朋友喜欢网络安全！ 最近，一种新的DDoS——脉冲波悄然来临。其基本原理是利用不同线路服务器的延时，使得Request同时到达目标服务器，以堵塞其它正常的通讯。 不妨假设攻击者在1号节点，目标服务器在$n$号节点，其余节点（2到n-1号节点）为中继服务器。 攻击者可以在任意时间发送一个定向数据包（即规定其经过中继服务器的路线，但不同数据包的路线不能完全相同），目标服务器对这种数据包具有100%的识别率，一旦识别到这种数据包，则会屏蔽这一时刻后的所有数据包。 Nancy好奇，攻击者在最优策略下，目标服务器能够收到多少份数据包呢？

输入描述:

第一行：两个整数n,m。接下来m行：每行三个整数x,y,z，表示节点x与y可以单向通信（x到y），耗时为z。数据满足：，，图为拓扑图（有向无环图）。

输出描述:

共一行：表示攻击者在最优策略下，目标服务器能够收到数据包的数量。由于数量可能会很大，你只需要输出答案对20010905取模后的值。