레인보우 그래프

Roy와 Biv는 정점이 $n$개인 무방향 그래프를 갖고 있다. 정점은 1부터 $n$까지 번호가 붙어 있다. 각 간선에는 양의 정수 가중치와 색이 있다. 색은 빨강, 초록, 파랑 세 가지뿐이다. 같은 두 정점을 잇는 간선이 여러 개 있을 수 있고, 자기 자신으로 가는 간선도 있을 수 있다.

양의 정수 $k$를 정하고, Roy와 Biv는 간선을 정확히 $k$개 고른 뒤 나머지 간선을 모두 지운다. 이후 두 사람 모두 그래프가 연결되어 있다고 봐야 한다. Roy는 빨강 간선을 볼 수 없고, Biv는 파랑 간선을 볼 수 없다. 따라서 파랑과 초록 간선만으로 모든 정점이 연결되어야 하고, 빨강과 초록 간선만으로도 모든 정점이 연결되어야 한다.

$k$가 1부터 $m$까지일 때마다, 두 사람 모두 연결되었다고 볼 수 있는 $k$개 간선의 가중치 합의 최솟값을 구하라.

첫 줄에 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 100$). 각각 정점 수와 간선 수이다. 이어지는 $m$개의 줄에는 정수 $a$, $b$ ($1 \le a, b \le n$), 가중치 $w$ ($1 \le w \le 1{,}000$), 색 $c$ ($c \in \{R, G, B\}$)가 주어진다. 정점 $a$와 $b$를 잇고 가중치가 $w$이며 색이 $c$인 간선을 뜻한다.

$m$개의 줄을 출력한다. $i$번째 줄에는 $k = i$일 때의 답을 출력한다. Roy와 Biv가 둘 다 그래프를 연결되었다고 볼 수 없으면 -1을 출력한다. 그렇지 않으면 두 사람 모두 연결되었다고 볼 수 있는 $k$개 간선 집합의 가중치 합의 최솟값을 출력한다.