交货提前期对于获取订单至关重要，在准备产品时，各种问题都会导致不同的提前期。例如，在不同工作区域之间切换的流程以及每个流程的工作量。生产经理在收到订单咨询时，应准确估算目标产品的提前期。请开发一个程序来帮助产品经理估算提前期。

咨询的提前期代表生产时间，包括物料准备、制造、质量检查、运输等多个作业。每个岗位的处理时间可以通过执行时间来确定，而将流程从一个作业转移到下一个作业则需要传输时间。对于一项咨询，生产经理拥有关于目标产品的三条信息：

• 作业和传输的数量，例如 $|T^j|$ 和 $|T^t|$，
• 每个作业的处理时间，其中 $T^j = \{t^j_0, t^j_1, t^j_2, \dots, t^j_{|T^j|-1}\}$，以及
• 作业之间的传输时间，其中 $T^t = \{t^t_0, t^t_1, t^t_2, \dots, t^t_{|T^t|-1}\}$。

流程可能以多个起始作业开始或结束。这种情况可以通过插入虚拟的起始作业和结束作业来简化问题。我们可以假设咨询流程包含一个起始作业和一个结束作业。

输入格式

输入包含三个部分：(1) 第一行是作业和传输的数量，(2) 第二行是作业处理时间，(3) 其余行是传输时间。输入的第一行包含 $|T^j|$ 和 $|T^t|$，中间用空格分隔。输入的第二行是 $T^j$，其中每个元素用逗号分隔。传输时间信息从第三行到第 $(2 + |T^t|)$ 行给出。每一行传输时间信息包含三个数据：源作业、目标作业和传输时间。

此外，测试用例还有一些限制：

• 任意一对作业之间最多只有一条传输时间。
• 一个文件中可能包含多个测试用例。

输出格式

应提供交付产品的总时间（记为 $z$），这意味着所有作业都应在 $z$ 时间内完成。此外，生产经理对制造过程也很感兴趣。如果存在唯一一条决定提前期的处理路径，请输出该处理路径的作业序列；否则，输出大写字母 “M”。输出序列中的每个元素用逗号分隔。换句话说，输出序列应为 “$z,v_1,v_2,\dots$” 或 “$z,M$” 的形式，其中 $v_1$ 和 $v_2$ 代表作业。

数据范围

每项咨询恰好包含一个入口和一个出口。在每项咨询中，至少有一条路径会决定提前期，这表明不存在循环制造过程。各变量的边界如下：

• $2 \le |T^j| \le 50$。
• $1 \le |T^t| \le 100$。
• $1 \le t^j_x, t^t_y \le 50$。

样例

输入 1

8 11
2,7,2,6,5,1,2,7
6 7 2
0 1 4
0 2 2
1 3 6
1 4 5
1 5 3
2 4 1
3 6 2
3 7 9
4 5 2
5 7 2

输出 1

41,0,1,3,7

输入 2

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

输出 2

53,0,1,4,5
53,M