Problems
We are trying to make a toy by assembling several kinds of parts.
To make this toy, basic parts and intermediate parts—made by assembling those basic parts—are used.
A basic part is one that cannot be assembled using other parts.
An intermediate part is one that is made by using other intermediate parts or basic parts.
For example, suppose basic parts are 1, 2, 3, and 4.
Intermediate part 5 is made from two basic part 1s and two basic part 2s.
And intermediate part 6 is made from two intermediate part 5s, three basic part 3s, and four basic part 4s.
Finally, the finished toy product 7 is made from two intermediate part 5s, three intermediate part 6s, and five basic part 4s.
In this case, the number of basic parts required to make the finished toy 7 is:
basic part 1 → 16 pieces, basic part 2 → 16 pieces, basic part 3 → 9 pieces, basic part 4 → 17 pieces.
Given the relationships between a toy's finished product and the parts required for it,
write a program that calculates the number of each basic part needed
to assemble one finished toy product.
Input
The first line of the input file contains an integer N (3 ≤ N ≤ 100).
Numbers 1 to N−1 represent basic parts or intermediate parts,
and N represents the finished product.
The next line contains an integer M (3 ≤ M ≤ 100).
Each of the following M lines provides three integers X Y K, describing a relationship.
This means:
“To make intermediate part or finished product X,
K pieces of intermediate part or basic part Y are required.”
Output
Print the number of basic parts required to assemble one finished product,
one line per basic part (intermediate parts are not printed).
You must print them in increasing order of the basic part number.
Each line should output the basic part’s number and the required quantity.
It is guaranteed that the total required quantity of all basic parts
does not exceed 10,000. (easy)
Example #1
7
8
5 1 2
5 2 2
7 5 2
6 5 2
6 3 3
6 4 4
7 6 3
7 4 5
1 16
2 16
3 9
4 17
Example #2
5
6
1 3 4
1 4 2
3 4 1
5 3 2
5 1 3
3 2 3
2 42
4 20
You must sign in to write code.