There is a running man running around the world.Now here are some places he will run to.Between two places exists distance.Now he is at A,he will go to B,C,D,E and else.

Input until EOF.
Input a positive integer t(1<t<10) in the first line.t means the number of places(From A to (A+t-1)).
Next line follows a integer n(1<n<20) means the existing loads.
Then follows n lines.Each line includes three parameters x,y,z(0<z<100).It means the running man runs from place x to place y for z distance.and he can not run from place y to place x.If there is unspecified from x to y,it means he can not run directly from x to y.

You should output the minimum distance from starting point(place A) to every other places.If he can not go to place y,you should output 'No'.