미친 회로

당신은 새 로봇을 위한 회로 기판을 막 완성했고, 이제 여기에 전원을 공급해야 합니다. 로봇 회로는 여러 개의 전기 부품으로 이루어져 있으며, 각 부품은 동작하기 위해 일정한 크기의 전류가 필요합니다. 모든 부품에는 + 단자와 - 단자가 있으며, 이들은 기판 위의 접점(junction)에서 서로 연결됩니다. 전류는 부품을 +에서 - 방향으로 흐릅니다(단, 부품은 전류를 '소모'하지 않습니다. +로 들어온 전류는 모두 그대로 -로 나갑니다).

접점에는 $1, \dots, N$ 번호가 매겨져 있고, 여기에 더해 전원 공급 단자가 연결되는 두 개의 특수 접점 +와 -가 있습니다. + 단자에는 부품의 + 리드만, - 단자에는 부품의 - 리드만 연결됩니다. 각 접점에서, 연결된 부품들의 - 리드로 들어온 전류는 모두 연결된 + 리드로 나가며, 각 + 리드로 얼마만큼의 전류를 보낼지는 당신이 자유롭게 조절할 수 있습니다(그 구체적인 방법은 이 문제의 범위를 벗어납니다). 또한 회로는 전류가 고리를 이루며 흐를 수 있는 되먹임 루프(feedback loop)가 존재하지 않도록 조립되어 있습니다.

그림 1: 올바른 회로도 두 가지 예. (a)에서는 모든 부품이 + 단자에서 - 단자로 향하는 방향 경로를 따라 전원을 공급받을 수 있습니다. (b)에서는 접점 4에서 - 단자로 가는 방향 경로가 없으므로 부품 4와 6에 전원을 공급할 수 없습니다.

전력을 아끼고 회로가 과열되지 않도록, 로봇을 동작시키는 데 필요한 전류를 가능한 한 적게 사용하고 싶습니다. 모든 부품이 각자 필요한 만큼의 전류를 공급받아 정상 동작하도록 하려면, + 단자로 흘려보내야 하는(그리고 반드시 - 단자로 모두 빠져나가는) 전류의 최솟값은 얼마입니까?

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $M$이 주어집니다. $N$ ($0 \le N \le 50$)은 +와 - 단자를 제외한 접점의 개수이고, $M$ ($1 \le M \le 200$)은 회로도에 있는 부품의 개수입니다. 이어지는 $M$개의 줄에는 각각 하나의 부품에 대한 설명이 주어집니다. $i$번째 부품 설명은 세 개의 필드로 이루어집니다: 부품이 연결된 +쪽 접점 $p_i$, -쪽 접점 $n_i$, 그리고 부품 $i$가 동작하는 데 필요한 최소 전류 $I_i$ ($1 \le I_i \le 100$)입니다. 접점 $p_i$와 $n_i$는 각각 + 단자를 뜻하는 문자 +, - 단자를 뜻하는 문자 -, 또는 번호가 매겨진 접점 중 하나를 뜻하는 $1$ 이상 $N$ 이하의 정수로 주어집니다. 어떤 두 부품도 +쪽 접점과 -쪽 접점이 동시에 같지는 않습니다. 입력의 끝은 $N = M = 0$인 잘못된 테스트 케이스로 표시되며, 이 케이스는 처리하지 않습니다.

각 테스트 케이스에 대해, 모든 부품이 전원을 공급받도록 보장하기 위해 + 단자에 공급해야 하는 전류의 최솟값을 정수 하나로 출력합니다. 만약 모든 부품에 동시에 충분한 전류를 보낼 방법이 없다면, impossible을 출력합니다.