描述：

    图的连接边上的数据表示其权值，带权值的图称作网。

<br />

<span style="font-size:10.5000pt;font-family:'宋体';">上图可描述为顶点集为</span><span style="font-size:10.5000pt;font-family:'Arial';">（<span>a,b,c,d,e)</span></span><span style="font-size:10.5000pt;font-family:'Arial';"></span> 

<span style="font-size:10.5000pt;font-family:'宋体';">边集及其权值为(始点，终点&nbsp;权值）：</span><span style="font-size:10.5000pt;font-family:'Arial';">a&nbsp;b&nbsp;3</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> 

<span style="font-size:10.5000pt;font-family:'Arial';">&nbsp;&nbsp;&nbsp;&nbsp;a&nbsp;c&nbsp;2&nbsp;</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> 

<span style="font-size:10.5000pt;font-family:'Arial';">&nbsp;&nbsp;&nbsp;&nbsp;b&nbsp;d&nbsp;5</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> 

<span style="font-size:10.5000pt;font-family:'Arial';">&nbsp;&nbsp;&nbsp;&nbsp;c&nbsp;d&nbsp;7</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> 

<span style="font-size:10.5000pt;font-family:'Arial';">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; c&nbsp;e&nbsp;4</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> 

<span style="font-size:10.5000pt;font-family:'Arial';">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; d&nbsp;e&nbsp;6</span><span style="font-size:10.5000pt;font-family:'Arial';"> </span><span style="font-size:10.5000pt;font-family:'Arial';">&nbsp;&nbsp;</span><span style="font-size:10.5000pt;font-family:'宋体';">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-size:10.5000pt;font-family:'宋体';"></span> 

<span style="font-size:10.5000pt;font-family:'宋体';">&nbsp;&nbsp;</span><span style="font-size:10.5000pt;font-family:'宋体';">网的源点是入度为0的顶点，汇点是出度为0的顶点。网的关键路径是指</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'Arial';background:#FFFFFF;">从源点到汇点的所有路径中，具有最大路径长度的路径</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">。上图中的关键路径为</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">a-&gt;c-&gt;d-&gt;e<span>，其权值之和为关键路径的长度为</span><span>15</span><span>。</span></span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> 

<span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">&nbsp;&nbsp;本题的要求是根据给出的网的邻接矩阵求该网的关键路径及其长度。</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> 

<br />

第一行输入一个正整数n（1<=n<=5)，其代表测试数据数目，即图的数目

第二行输入x(1<=x<=15)代表顶点个数，y(1<=y<=19)代表边的条数

第三行给出图中的顶点集，共x个小写字母表示顶点

接下来每行给出一条边的始点和终点及其权值，用空格相隔，每行代表一条边。

第一个输出是图的关键路径（用给出的字母表示顶点， 用括号将边括起来，顶点逗号相隔）

第二个输出是关键路径的长度

每个矩阵对应上面两个输出，两个输出在同一行用空格间隔，每个矩阵的输出占一行。