No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard

output: 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.

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 the length of the shortest path between the first and the N-th vertexes. Output "-1" if the path doesn't exist.

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: | --- |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/22/2019 19:04:59 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|