problem link 339C - Ксюша и гири

The editorial of this problem tells us to make a graph of nodes where each node is a tuple (i,j,k). And after making this node we have to find a path from (0,0,1) to some node (x,y,m). Now according to the question, this graph is acyclic and directed. And each node can have 9 outdegree (there are 10 weights to select from but we cant select the previous weight). And the length of the path is m<=1000. Now i cant find a way to find the path from (0,0,1) to (x,y,m). Because i think there can be 9^(1000) possible paths. How to prove that the number of paths we have to check will actually be less so that we dont get a TLE. Please Help!!