eolymp
bolt
Try our new interface for solving problems
Problems

Triangles

Triangles

Time limit 1 second
Memory limit 64 MiB

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 data

The first line of the input file contains two space-delimited numbers N and M (2N1000, 0M3000) — 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 data

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

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.

Examples

Input example #1
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
Output example #1
4
Source 2013-2014 ACM Central Region of Russia Quarterfinal, Rybinsk 2013/10/17