NAJKRACI - Najkraci

## 题目描述 一个城市的道路网包括$n$个点$m$条有向边，点编号$1$到$n$，对于每条边，求出有多少条不同的最短路包括了这条边，答案对$1e9 + 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)，边权应该是非负数

A road network in a country consists of N cities and M one-way roads. The cities are numbered 1 through N. For each road we know the origin and destination cities, as well as its length. We say that the road F is a continuation of road E if the destination city of road E is the same as the origin city of road F. A path from city A to city B is a sequence of road such that origin of the first road is city A, each other road is a continuation of the one before it, and the destination of the last road is city B. The length of the path is the sum of lengths of all roads in it. A path from A to B is a shortest path if there is no other path from A to B that is shorter in length. Your task is to, for each road, output how many different shortest paths containing that road, modulo 1 000 000 007.

The first line contains two integers N and M (1 ≤ N ≤ 1500, 1 ≤ M ≤ 5000), the number of cities and roads. Each of the following M lines contains three positive integers O, D and L. These represent a one-way road from city O to city D of length L. The numbers O and D will be different and L will be at most 10000.

Output M integers, each on its own line – for each road, the number of different shortest paths containing it, modulo 1 000 000 007. The order of these numbers should match the order of roads in the input.

4 4
1 2 5
2 3 5
3 4 5
1 4 8

2
3
2
1

Input:
5 8
1 2 20
1 3 2
2 3 2
4 2 3
4 2 3
3 4 5
4 3 5
5 4 20

Output:
0
4
6
6
6
7
2
6