Implement the Floyd-Warshall graph algorithm. Display the final distance and parent matricies.

INPUT

Read, from STDIN, the complete set of directed edges, one edge per line. Source node, Destination Node, and Weight for that edge will be integers separated with a comma, and/or whitespace, and given in that order. Nodes will be identified by contiguous integers starting at 1. The number of nodes can be infered from the highest index to be identified by an edge.

OUTPUT

Output, to STDOUT, a nicely formatted final distance matrix and a parent matrix. Rows and Colums must be properly aligned and labeled. Your output line length need not be limited by the terminal line widthlarger output will be redirected to a file.

SAMPLE INPUT

1 8 5 1 11 2 1 1 12 5 4 -2 1 3 11 1 10 8 12, 8, 10 12, 11, 8 12, 7, 6 6, 5, -3 12 9, 4 12,2 1 12,5,9 6,7,-1