226. Colored graph

time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



You are given an oriented graph. Each edge of the graph is colored in one of the three colors. Your task is to find the length of the shortest path from the first vertex to the N-th. Note that any two successive edges in the path can't have the same color.

Input
The first line of the input file consists of two integers N and M (2 <= N <= 200; 0 <= M <= N*N). Next M lines contain descriptions of the edges. Each edge description is a list of three integers X, Y, C (1 <= X, Y <= N, 1 <= C <= 3), where X is the starting vertex of the edge, Y is the finishing vertex and C is the color of the edge.

Output
Output the length of the shortest path between the first and the N-th vertexes. Output "-1" if the path doesn't exist.

Sample test(s)

Input
 
Test #1 
4 4 
1 2 1 
2 3 2 
3 4 3 
2 4 1 
 
Test #2 
3 2 
1 2 1 
2 3 1 
 

Output
 
Test #1 
3 
 
Test #2 
-1 
 
  
  
Author:--- 
Resource:--- 
Date:---