URI Online Judge | 3177

Santa's Toy Factory

By Arthur Haas Dorneles, URI BR Brazil

Timelimit: 1

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.

Input

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; NM≤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 YN; 1≤ Z ≤ 20).

Note: House 1 and house N represent Santa's material inventory and toys warehouse respectively.

Output

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
1 2 7
1 3 17
1 4 16
2 6 4
2 4 3
3 4 7
3 6 13
4 6 18
4 5 6
4 7 11
5 7 20
6 5 9
6 7 15
5 4
1 4 19
1 2 7
2 4 13
3 5 20

40
Nao eh possivel produzir nenhum brinquedo