장난감 조립

어떤 장난감 완제품은 여러 부품을 조립해서 만든다. 부품에는 다른 부품 없이 바로 사용할 수 있는 기본 부품과, 기본 부품 또는 다른 중간 부품을 조립해서 만드는 중간 부품이 있다.

완제품과 각 부품 사이의 조립 관계가 주어질 때, 완제품 하나를 만드는 데 필요한 기본 부품의 종류별 개수를 계산해야 한다.

첫째 줄에 자연수 N이 주어진다. 1부터 N-1까지는 기본 부품 또는 중간 부품의 번호이고, N은 완제품의 번호이다. (3 <= N <= 100)

둘째 줄에 자연수 M이 주어진다. (3 <= M <= 100)

다음 M개의 줄에는 세 자연수 X, Y, K가 주어진다. 이는 중간 부품 또는 완제품 X를 만들기 위해 부품 Y가 K개 필요하다는 뜻이다.

두 중간 부품이 서로를 필요로 하는 경우는 없다.

완제품 하나를 조립하는 데 필요한 기본 부품의 번호와 개수를 한 줄에 하나씩 출력한다. 중간 부품은 출력하지 않는다.

기본 부품 번호가 작은 순서대로 출력하며, 각 줄에는 기본 부품 번호와 필요한 개수를 공백으로 구분해 출력한다.

정답은 2,147,483,647 이하이다.