Santa's Toy Factory
By Arthur Haas Dorneles, URI 
Brazil
By Arthur Haas Dorneles, URI Brazil
Due to covid-19, Santa's toy factory had to be shut down. Not to cancel the festivities, the elves had to work at home. Unfortunately, work at home causes some complications in logistics and transportation. To solve this problem was organized conveyor lines between the elves' houses. Due to natural conditions and distance between those houses, each line has a transport limit.
The elf manager Jean asked you, a very good elf in programming, to make an algorithm to solve the problem. You must calculate what is the largest amount of toys that can be transported to the toys warehouse.
The input consists of several test cases. The first line contains two integers N and M, which represents the number of elves responsible for making the toys and the number of conveyor lines, respectively (1≤N≤30; N≤M≤55). The next M lines contain three integers X, Y, and Z, X being the house of origin, Y the house of destination, and Z the maximum that can be transported (1≤X and Y≤ N; 1≤ Z ≤ 20).
Note: House 1 and house N represent Santa's material inventory and toys warehouse respectively.
For each test case, your algorithm should print a line with an integer, representing the largest possible number of toys, if possible to produce a toy, otherwise it should print "Nao eh possivel produzir nenhum brinquedo".
| Input Sample | Output Sample |
|
7 13 |
40 |