전초기지 경로 탐색

도시가 좀비에게 점령당했고, 당신의 팀은 보급품이 거의 떨어졌다. 꼼꼼한 정찰과 계획 끝에 안전한 전초기지 목록과 각 도로에서 목격된 좀비 수를 정리한 지도를 손에 넣었다. 전초기지는 모두 같은 무전망에 속해 있고, 각자의 무전 호출부호를 지명으로 쓴다.

팀이 챙긴 탄약은 한정되어 있어서 일정 규모까지의 좀비 무리만 막아낼 수 있다. 탄약 한 발은 한 번의 이동에서 좀비 한 마리를 막아낸다. 도로 하나를 안전하게 지나가려면 그 도로에서 마주치는 좀비 수만큼 탄약을 써야 한다. 정찰 자료를 보고, 필요한 보급품이 있는 전초기지까지 가는 안전한 경로 중에서 좀비를 가장 적게 마주치는 경로를 찾아라.

출발지는 목록의 첫 번째 전초기지이고, 그곳에 있는 탄약을 모두 가지고 출발한다. 필요한 보급품은 없지만 탄약이 있는 전초기지가 출발지 말고 최대 한 곳 더 있을 수 있다. 그 전초기지까지 이동하면 거기 있는 탄약을 전부 챙길 수 있다. 필요한 보급품이 있는 전초기지는 몇 곳이든 있을 수 있지만, 그중 한 곳에만 도착하면 된다.

같은 도로를 여러 번 지나야 한다면 지날 때마다 처음과 같은 수의 좀비를 다시 마주치고, 그 좀비도 마주친 좀비 수에 그대로 더해진다. 좀비는 총알로 쉽게 죽지 않는다.

첫째 줄에 테스트 케이스의 수 $C$ ($1 \le C \le 50$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 전초기지의 수 $N$ ($1 \le N \le 100$)과 도로의 수 $R$ ($0 \le R \le 200$)이 공백으로 구분되어 주어진다.

이어지는 $N$개의 줄에는 전초기지 정보가 한 줄에 하나씩 주어진다. 각 줄에는 호출부호, 그 전초기지에 있는 탄약의 양 $A$ ($0 \le A \le 100$), 필요한 보급품이 있는지를 나타내는 문자열이 순서대로 주어진다. 호출부호는 알파벳 대문자 A부터 Z까지와 숫자 0부터 9까지로 이루어진 6글자이고, 마지막 문자열은 yes 또는 no이다. 목록의 첫 번째 전초기지가 출발지이다.

이어지는 $R$개의 줄에는 도로 정보가 한 줄에 하나씩 주어진다. 각 줄에는 도로가 잇는 두 전초기지의 호출부호와 그 도로에서 마주치는 좀비의 수 $Z$ ($0 \le Z \le 100$)가 순서대로 주어진다. 도로는 양방향으로 지날 수 있다.

각 테스트 케이스마다 한 줄에, 필요한 보급품이 있는 전초기지까지 가는 안전한 경로에서 마주치는 좀비 수의 최솟값을 출력한다. 안전한 경로가 하나도 없으면 대신 No safe path를 출력한다.