Colors

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\}$