Recently I saw this question , and I got the idea that it will be solved using bfs/dfs , but couldn’t reach the final working algorithm .Can someone help me with this?

Suppose there is a city of N towns and M bidirectional roads where a strict mayor has set of certain rules.

Rule 1: men can walk only on roads marked by type 1 or 3.

Rule 2: women can walk only on roads marked by type 2 or 3.

He now thought to renovate the city by reconstructing some roads but with a condition that the normal routine of the citizen should not be hampered. You are hired to do the duty. So he asks you – What is the maximum number of roads it’s possible to destroy that the city will be still connected to both men and women?

The city is said to be connected if it’s still possible to travel from town X to town Y using the existing roads.

Input

The first line contains 2 space-separated integers: N and M.

Each of the following M lines contains description of one edge: three different space-separated integers: A, B, and C.

A and B are different and from 1 to N each and denote numbers of vertices that are connected by this edge. C denotes the type of this edge.

Output

For each test case output one integer - the maximal number of roads it’s possible to destroy or -1 if the town is not connected initially for both men and women.

Constraints

1 <= N <= 1000

1 <= M <= 10000

1 <= A, B <= N

1 <= C <= 3