Tanya and Nina are very close friends, still Tanya is jealous of Nina's problem solving skills. To prove Nina that she is even better than her, Tanya challenged Nina in a game known as Connecting the Dots which she described to her as follows:

There are N dots numbered from 1 to N.

M pair of dots are connected to each other using a ray pointing from one dot to other.

Each ray will be of one of the K colors.

The objective of the game is to reach dot N starting from dot 1 moving on minimum number of rays pointing from one dot to another.

Nina interrupted Tanya and said "Ohh thats so easy!". Tanya smiled and said, "Wait a moment dear, it's not yet over. There is a special constraint to the above problem i.e. the path of rays connecting dot 1 and dot N should be such that no two successive edges are of the same color, and the path of rays to Node N from Node 1 should be the shortest."

Nina thought for a while bu then realized that the number of dots could be large enough to calculate the answer manually, so she seeks your help.

Input:

The first line of the input file consists of two integers N and M (). Next M lines contain descriptions of the rays.

Each ray description is a list of three integers X, Y, C which means there exists a C colored ray starting from dot X and pointing to dot Y. All the 3 integers are separated by a single space.

Output:

Print the length of the shortes path between the first dot and the N'th dot. Print "-1" if no such path exists.

Constraints:

2 <= N <= 1000

0 <= M <= N*N

1 <= X, Y <= N

1 <= C <= 3

Update: A test file for the problem Connecting the dots has been removed, and hence the points for the problem is decreased by 5.