connecting-the-dots

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.

SAMPLE INPUT
4 4
1 2 1
2 3 2
2 4 1
3 4 3

SAMPLE OUTPUT
3

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: