최소 비용 유향 트리

정점이 $N$개이고 간선이 $M$개인 방향 그래프와 루트 정점 $R$이 주어진다. 정점의 번호는 $0$부터 $N-1$까지이다. 간선 비용은 정수이며 음수일 수도 있다. 자기 루프와 중복 간선이 있을 수 있다.

간선 $N-1$개를 선택하여 $R$에서 모든 정점에 도달할 수 있게 만들려고 한다. 선택한 간선의 비용 합의 최솟값을 구해 보자. 조건을 만족하는 간선을 선택하지 못할 수도 있다.

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 200)$

각 테스트 케이스의 첫 번째 줄에 세 정수 $N$, $M$, $R$이 공백으로 구분되어 주어진다. $(1 \le N \le 2\,000; 0 \le M \le 40\,000; 0 \le R < N)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 시작 정점 번호 $u$, 끝 정점 번호 $v$와 정수 비용 $w$가 공백으로 구분되어 주어진다. $(0 \le u, v < N; -10^9 \le w \le 10^9)$

전체 테스트 케이스에서 $N$의 합은 $20\,000$ 이하이고 $M$의 합은 $200\,000$ 이하이다.

각 테스트 케이스마다 고른 간선의 비용 합의 최솟값을 한 줄에 출력한다. 조건을 만족하는 간선을 고를 수 없다면 IMPOSSIBLE을 출력한다.