Road Reform
The road network of Byteland can be described as a graph with nodes, describing the cities, and edges, describing the roads. Historically, all the roads are toll roads, so each road has positive integer cost associated with it. Moreover, all the roads are bidirectional and you can reach any city from any other city of Byteland by roads.
Historically, there are two capital cities in Byteland - ByteCity and St. Byteburg. They are described as the nodes with the numbers and respectively.
Now it's time for a road reform in Byteland. The treasury has enough funds for building exactly one bidirectional road with an arbitrary positive integer cost between any pair of different cities. In order for the reform to be efficient, there is a requirement that the shortest distance between ByteCity and St. Byteburg should decrease.
Please count the number of ways the road reform can be performed, i.e. find the number of ways to build a road with a positive integer cost between an unordered pair of different cities so that the distance between the cities and decrease.
Input Format
The first line contains two space-separated integers, and , denoting the number of cities and the number of roads respectively.
Each of the following lines contain three integers, , , and , that describe a road connecting the cities with the numbers and and has the cost .
There can be multiple roads connecting the same pair of cities. You can also build a road that connects some pair of cities that are already directly connected with a road.
Constraints
It is possible to reach any city from any other city using the given road network.
Output Format
Output the number of ways to perform the road reform on a single line.
Sample Input
3 3
1 3 4
1 2 1
2 3 2
Sample Output
3
Explanation
The shortest distance between the cities and equals to . Here's the list of roads that can be added so that the shortest distance decreases.
- A road between the cities and with a cost .
- A road between the cities and with a cost .
- A road between the cities and with a cost .