Problem Statement  
This problem statement contains an image which will not display correctly for plugin users. You will be given an undirected graph which may contain several smaller copies of itself. These copies, or "children", will in turn recursively contain the same number of children, creating a graph with an infinite number of nodes. You are to find the shortest path through this graph. At each level down, the edges of children have half the weight of their parent, rounded down. Once you recurse deep enough into the graph, all edges eventually have a weight of zero.
For example, consider the graph pictured above with 4 toplevel nodes (A, B, C, and D), and 2 recursive children. Notice that each child has two smaller copies inside of it, and each of those children has two smaller copies inside of it, repeating infinitely. In this graph, there is a direct path from node A to B with distance 800. However, there is a shorter path from A to B that goes through C and D in the leftside child of the toplevel graph. Within the leftside child, the path from C to D goes through A and B in its rightside child. The length of this 5edge path is 4 + 2 + 200 + 2 + 4 = 212. However, there is an even shorter path, bypassing the thirdlevel edge from A to B with cost 200. By replacing this edge with the same 5edge path two levels down, there is a 9edge path with distance 4 + 2 + 1 + 0 + 50 + 0 + 1 + 2 + 4 = 64. Similarly, the edge with cost 50 can be bypassed again by recursing farther into the graph. By going down deep enough to the point where all edges have zero weight, the edge cost can be bypassed completely, resulting in a shortest path from A to B of length 4 + 2 + 1 + 0 + ... + 0 + 1 + 2 + 4 = 14. Graphs will contain up to 10 toplevel nodes ('A' through 'J'), and each parent graph at each level may contain up to 9 child graphs, smaller copies of itself, numbered ('1' through '9'). The graph will be specified by a list of edges in the toplevel graph. Edges are specified by two nodes, followed by a weight. Either node may optionally be followed by a single digit, representing a connection to a node in the corresponding recursive copy of the graph. The graph pictured above would be specified as: "A B 800" (connecting A and B in every copy of the graph) "A C1 4" (connecting A in every copy to C in its first child) "D1 B 4" (connecting B in every copy to D in its first child) "C A2 4" (connecting C in every copy to A in its second child) "B2 D 4" (connecting D in every copy to B in its second child) There will be no edge that directly connects two nodes of the same child. For example, the edge "A3 B3 10" would be illegal, but the edge "A4 B5 20" is allowed. A toplevel edge implies corresponding edges in all copies of the graph at all levels. Likewise, an edge connecting a toplevel node to a copy implies corresponding connections between parents and children at all levels, and an edge connecting nodes of two different children implies corresponding edges between nodes in those two children at all levels. Given a list of edges, a starting node, and an ending node, return the length of the shortest path between the starting and ending nodes. Return 1 if there is no such path, or if the distance of the shortest path is greater than 1,000,000,000.  
Definition  
 
Notes  
  The shortest path may descend recursively down many levels.  
  All edges are undirected. The order of a pair of nodes in the input is not significant.  
  There can be no edges that connect nodes between levels with depths that differ by more than 1.  
Constraints  
  edges will contain between 1 and 50 elements, inclusive.  
  Each element of edges will be formatted as "<node> <node> <weight>".  
  Each <node> is a character between 'A' and 'J', inclusive, optionally followed by a digit between '1' and '9', inclusive.  
  Each <weight> is an integer from 0 to 1000, inclusive, and will not have any leading zeros.  
  There will be at most 10 toplevel nodes (letters 'A' through 'J').  
  At each level, there will be at most 9 copies of the graph embedded directly in itself (nodes with digits '1' through '9').  
  There will not be more than one edge between the same two nodes.  
  There will not be an edge connecting two nodes of the same recursive copy, i.e. "A1 B1 5" would be illegal input.  
  start and end will each be a character between 'A' and 'J', inclusive, and will be nodes which appear in edges.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
 
4)  
