题号：NC225185
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
xay is competiting on the Internet. He spends 0.1 seconds thinking about it, then he quickly codes “Floyd" algorithm.
"Floyd" is a Well-Known algorithm. It can be represented as:
for k from 1 to n for i from 1 to n for j from 1 to n dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j])However, xay can't remember how to write it. Then he writes down:
for i from 1 to n for j from 1 to n for k from 1 to n dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j])Although xay makes a mistake, he still want to calculate how many
If u can't reach v , then
输入描述:
The first line contains two integers n and m .
The following m lines, each line contains three integers u,v,w , denoting there is a directed edge from u to v , and the weight is w , i.e. dis[u][v]=w .It's guaranteed that (u,v) appears at most once.It's guaranteed
输出描述:
Output the answer.
示例1