SP3545 NAJKRACI - Najkraci

一个城市的道路网包括 $n$ 个点 $m$ 条有向边，点编号 $1$ 到 $n$，对于每条边，求出有多少条不同的最短路包括了这条边，答案对 $10^9 + 7$ 取模。

第一行两个数 $n,m$，表示点的个数和有向边数。 接下来 $m$ 行，每行有三个数 $u,v,d$ 表示边的起点，终点和边权。

输出 $m$ 行，每行输出对于该边，有多少条不同的最短路包括它。必须按照输入给定边的顺序输出。

对于 $100 \%$ 的数据，保证 $1 \leq n \leq 1500$,$1 \leq m \leq 5000$,$1 \leq u,v \leq n$,$u \ne v,d \leq 10000$。 译者注：[COCI原题面链接](http://www.hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf)，边权应该是非负数