Marcy 正在参加骄傲节（Pride Fest），并报名参加了彩虹路跑比赛（Rainbow Road Race）。在每条街道上，都有准备了彩色粉笔灰的志愿者。当参赛者沿着街道行走时，志愿者会向他们身上撒粉笔灰。每条街道上撒的粉笔灰是彩虹七色之一：红（Red, R）、橙（Orange, O）、黄（Yellow, Y）、绿（Green, G）、蓝（Blue, B）、靛（Indigo, I）、紫（Violet, V）。一旦有人开始沿着某条街道行走，他们必须走到该街道的尽头。

比赛起点设在节日帐篷（Festival Tent）。比赛的目标是收集到所有颜色的粉笔灰并返回帐篷。请帮助 Marcy 确定她收集齐所有颜色并返回帐篷所需行进的最短距离。

图 1：左图对应样例输入 1，右图对应样例输入 2。三角形代表节日帐篷。

输入格式

输入的第一行包含两个整数 $n$ ($7 \le n \le 7^3$) 和 $m$ ($7 \le m \le 7^4$)，分别表示节日中的娱乐地点数量和连接这些地点的街道数量。娱乐地点的编号为 $1, \dots, n$，其中节日帐篷位于地点 1。

接下来的 $m$ 行描述这些街道。每行包含三个整数 $\ell_1, \ell_2$ ($1 \le \ell_1 < \ell_2 \le n$) 和 $d$ ($1 \le d \le 7^5$)，后跟一个字符 $c$（$c$ 是 R、O、Y、G、B、I、V 之一）。这表示该街道连接地点 $\ell_1$ 和 $\ell_2$，长度为 $d$ 米，且撒上的粉笔灰颜色为 $c$。

保证任意两个娱乐地点之间总是连通的。任意两个地点之间最多只有一条街道，且每种颜色至少出现一次。

输出格式

输出 Marcy 收集齐所有颜色并返回节日帐篷所需行进的最短距离。

样例

输入样例 1

7 7
1 2 1 R
2 3 1 O
3 4 1 Y
4 5 1 G
5 6 1 B
6 7 1 I
1 7 1 V

输出样例 1

7

输入样例 2

8 7
1 2 1 R
1 3 1 O
1 4 1 Y
1 5 1 G
1 6 1 B
1 7 1 I
1 8 1 V

输出样例 2

14