Colors

Grindra finds themself in a directed graph of ~n~ nodes and ~m~ edges. Furthermore, each node is painted a color, initially "Red". As Grindra is in possession of a paintbrush, they are also able to paint the nodes.

Each edge is of the form a b c d e, meaning that if Grinda is at node ~a~ when it is painted color ~b~, they can paint node ~c~ color ~d~, and the move to it with cost ~e~.

As Grindra's painting companion, can you help them answer the question: What is the minimum cost with which they can move from node ~0~ to node ~n-1~.

Input Format

The first line will consist of two integers, ~n~ and ~m~. The next ~m~ lines will each consist of 5 integers a b c d e, as described above.

Output Format

A single integer, the smallest cost to get from node ~0~ to node ~n-1~, assuming that every node starts as red.

Example Input 1

5 5
0 Red 1 Red 10
1 Red 2 Blue 10
0 Green 2 Blue 5
2 Blue 4 Green 5
1 Red 4 Blue 5

Example Output 1

10

Example Explanation 1

The optimal path is from (0, Red) to (2,Blue) to (4,Green). This has cost 10.

Constraints

~2 \le n \le 5e4 ~

~n-1 \le m \le n*10~

~0 \le a,c \le n-1~

~b,d \in \{Red,Green,Blue,Yellow,Brown\}~