You are given a flow graph G. The flow graph G has N vertices numbered from 1 to N. 1 is Source and N is Sink.
There is no incoming edge into Source and no outgoing edge from Sink. There is either edge (u,v) or (v,u) in G. You are also given the capacity of each edges. Assume all capacities are positive integers.
You calculated the maximum flow value in G. Now capacity of exactly one edge is increased by some positive integer value but not more than 1000.
And you found that there was no change in maximum flow.
Now your task is to find out that how many such edges are present in the graph G.

Input

First line will contain two integers N and E separated by space, where N is the number of vertices and
E is the number of edges.
Next E lines will contain 3 integers u, v and c separated by space. Which means is that there is an edge from u to v having capacity c.

Output

You have to output an integer which is the number of edges(one at a time) for which increase in their capacity by not more than 1000 will not lead to increase in maximum flow.

Input Constrain:

2

Example:

Input: 4 5 1 2 8 1 3 10 2 3 5 2 4 2 3 4 3 Output: 3

Explanation:

Increasing the capacity of edge (1,2),(1,3) and (2,3) (INDIVIDUALLY) does not have any effect on maximum flow.