该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

Bob对图非常感兴趣。

Bob有一张$N$个点$M$条边的带权有向图，点和边的编号都从$1$开始。

Bob可以派出一名哨兵，令其侦察点$x$。该哨兵将会从$1$出发，经过若干条边到达点$x$。该次侦察的费用为经过的所有边权之和。随后，哨兵会将此次侦察经过的边依次记录，形成一个数列$d$，我们称$d$为此次侦察的路径，而$\left|d\right|$则代表这条路经过的边数。

Bob将分$N$天对所有节点进行侦察。其中，第$i$天Bob会派出哨兵侦察点$i$。我们无法预测哨兵侦察的路径，但我们知道，聪明的哨兵一定会选择费用最小的路径之一。为了确保侦察在Bob的掌控中，他找到了你，希望你能找出每天哨兵的所有可能路径。

定义$n_i$代表第$i$天可能的路径总数，$d_{i,k}$代表第$i$天哨兵的第k种可能路径（$k=1,\ldots,n_i$）。方便起见，你只需要告诉他下列式子的计算结果即可：

可以证明，对于任意$i=1,\ldots,N$，答案并不受$d_{i,1},d_{i,2},\ldots,d_{i,n_i}$的顺序影响。

输入格式

第一行两个整数$N,M$。

接下来$M$行每行三个整数$s,e,d$代表有一条权值为$d$的从$s$到$e$的边。

输出格式

输出一行答案对${10}^9+7$取模之后的结果。

样例输入

3 3

1 2 1

2 3 2

1 3 3

样例输出

2

【数据规模与约定】

对于30%的数据，$N\le10$。

对于另外20%的数据，$d=1$。

对于另外20%的数据，$s<e$。

对于100%的数据，$1\le\ N\le{10}^5,1\le\ M\le2\times{10}^5,1\le\ s,e\le\ N,1\le\ d\le{10}^3$。