ICPC, 다시 파업하다

International Concrete Projects Company(ICPC)는 고급 주택 시장을 전문으로 하는 건설 회사이다. 작년부터 주택 개발 사업에 사용해 온 매우 효율적인 토지 분할 기법 덕분에, ICPC는 세계에서 가장 수익성이 높은 회사가 되었다.

최근 ICPC에 큰 혼란이 있었다. 직원들이 급여가 충분하지 않다며 일하기를 거부한 것이다. 파업으로 인한 이익 손실을 걱정한 이사회는 새로운 급여 계산 방식을 제안했고, 다행히 모두가 이를 받아들였다.

직원의 급여는 그가 수행하는 작업들의 중요도를 반영하며, 이 중요도는 작업들이 서로 어떻게 의존하는지에 따라 달라진다.

작업 $X$가 작업 $Y$에 의존한다는 것은, (i) $X$가 $Y$에 직접 의존하거나, (ii) 어떤 작업 $Z$가 존재하여 $X$가 $Z$에 직접 의존하고 그 $Z$가 다시 $Y$에 의존하는 경우를 말한다. ICPC에서는 모든 작업이 반드시 수행되어야 하므로, 의존 관계에는 순환이 존재하지 않는다. 또한 하나의 작업을 여러 명의 직원이 수행할 수도 있다.

각 작업에는 그 중요성을 나타내는 기본 중요도가 있다(예를 들어 효율적인 토지 분할 기법을 개발하는 일은 실제로 집을 짓는 일보다 더 중요하다). 작업 $T$의 중요도는 $T$의 기본 중요도에, $T$에 직접 의존하는 모든 작업의 중요도를 더한 값으로 정의된다. 특히 어떤 작업도 $T$에 직접 의존하지 않는다면, $T$의 중요도는 기본 중요도와 같다.

직원의 급여는, 그 직원이 수행하는 작업들 중에서 그 직원이 수행하는 다른 어떤 작업에도 의존하지 않는 작업들의 중요도를 모두 더한 값이다. 다시 말해, 직원 $W$가 작업 $X$를 수행할 때, $W$가 함께 수행하면서 $X$가 의존하는 다른 작업 $Y$가 존재하지 않는 경우에만 $X$의 중요도가 $W$의 급여에 더해진다.

각 직원의 급여를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $T$와 $E$가 주어지며, 각각 작업의 수와 직원의 수이다($1 \le T \le 1000$, $1 \le E \le 1000$). 작업은 $1$번부터 $T$번까지, 직원은 $1$번부터 $E$번까지 번호가 매겨져 있다.

그다음 작업 $1$번부터 $T$번까지의 설명이 번호 순서대로 주어진다. 각 작업은 두 줄로 설명된다. 첫 줄에는 세 정수 $BS$, $ND$, $NE$가 주어지며, 각각 그 작업의 기본 중요도, 그 작업에 직접 의존하는 작업의 수, 그 작업을 수행하는 직원의 수이다($1 \le BS \le 1000$, $0 \le ND < T$, $1 \le NE \le E$). 둘째 줄에는 $ND + NE$개의 정수가 주어지는데, 먼저 이 작업에 직접 의존하는 $ND$개의 작업 번호가, 이어서 이 작업을 수행하는 $NE$명의 직원 번호가 나온다.

입력의 끝은 $T = E = 0$인 줄로 표시되며, 이 줄은 처리하지 않는다.

테스트 케이스는 주어진 순서대로 답해야 한다. 각 테스트 케이스마다 다음을 출력한다.

• 케이스의 시작을 나타내는, 별 다섯 개 *****로 이루어진 한 줄
• 각 직원 $i$에 대해, 두 정수 $i$와 $s$를 공백 하나로 구분하여 한 줄에 출력한다. 이는 직원 $i$의 급여가 $s$임을 의미한다.