Дистанционный практикум по программированию

N nails are hammered in the wall. Some pairs of nails are connected with wires, possibly multiple. You may assume that there are no wires connecting nail to itself. Each wire is colored: white, blue, or red. We say that three wires form a triangle if there is a cycle connecting three nails. We call a triangle multi-colored if it is formed by wires of three distinct colors.

Write a program to compute the number of multi-colored triangles for a given list of wires.

 

Input

The first line of the input file contains two space-delimited numbers N and M—the number of nails and the number of wires. Each of the following M lines contains three integers: numbers of nails being connected by a wire, and the color of that wire. The color is indicated by integers 1, 2, or 3.

 

Output

The output file should contain a single integer, the number of multi-colored triangles.

 

Limitations

2 ≤ N ≤1000

0 ≤ M ≤ 3000

Example

Input	Output
4 8 1 2 1 1 3 1 2 3 1 1 3 2 1 4 3 1 4 3 4 3 1 3 4 2	4

 

Example explanation

The multi-colored triangles are formed by the following triples of wires:

·        (1,3,1), (3,4,2), (1,4,3);

·        (1,3,1), (3,4,2), (1,4,3);

·        (1,3,2), (4,3,1), (1,4,3);

·        (1,3,2), (4,3,1), (1,4,3).

 

Please note. In the example, the first and the second triangles, as well as the third and the fourth ones seem to be identical, however, given that there are two wires of the same color between the nails #1 and #4, the triangles are considered to be different as different wires are used to form the triangles.