时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
Nancy的男朋友喜欢网络安全！
最近，一种新的DDoS——脉冲波悄然来临。其基本原理是利用不同线路服务器的延时，使得Request同时到达目标服务器，以堵塞其它正常的通讯。
不妨假设攻击者在1号节点，目标服务器在$n$号节点，其余节点（2到n-1号节点）为中继服务器。
攻击者可以在任意时间发送一个定向数据包（即规定其经过中继服务器的路线，但不同数据包的路线不能完全相同），目标服务器对这种数据包具有100%的识别率，一旦识别到这种数据包，则会屏蔽这一时刻后的所有数据包。
Nancy好奇，攻击者在最优策略下，目标服务器能够收到多少份数据包呢？
最近，一种新的DDoS——脉冲波悄然来临。其基本原理是利用不同线路服务器的延时，使得Request同时到达目标服务器，以堵塞其它正常的通讯。
不妨假设攻击者在1号节点，目标服务器在$n$号节点，其余节点（2到n-1号节点）为中继服务器。
攻击者可以在任意时间发送一个定向数据包（即规定其经过中继服务器的路线，但不同数据包的路线不能完全相同），目标服务器对这种数据包具有100%的识别率，一旦识别到这种数据包，则会屏蔽这一时刻后的所有数据包。
Nancy好奇，攻击者在最优策略下，目标服务器能够收到多少份数据包呢？
输入描述:
第一行：两个整数n,m。
接下来m行：每行三个整数x,y,z，表示节点x与y可以单向通信（x到y），耗时为z。
数据满足：，
，图为拓扑图（有向无环图）。
输出描述:
共一行：表示攻击者在最优策略下，目标服务器能够收到数据包的数量。由于数量可能会很大，你只需要输出答案对20010905取模后的值。