Berland Post 是 Berland 的国家邮政服务。Berland 的每个城市都有且仅有一个邮局。城市及其对应的邮局编号为 $1$ 到 $n$。

有 $m$ 对城市 $(a, b)$ 之间存在直接的邮政往来。对于每一对这样的城市，投递时间是已知的：形式化地说，给定 $m$ 个三元组 $(a_j, b_j, d_j)$，意味着每天 $a_j$ 的邮局必须向 $b_j$ 的邮局发送信件，$d_j$ 是从 $a_j$ 发出到 $b_j$ 收到信件所经过的时间。

每天，所有邮局必须开放相同的连续时长，记为 $T$。但开放时间可能不同。如果第 $i$ 个邮局的开放时间为 $o_i$，则关闭时间为 $o_i + T$。

部分 $o_i$ 的值是已知且固定的，但有些则由你决定。你的目标是找到满足 $T \ge 0$ 的值以及 $o_i$，使得每个邮局都能在关闭时间之前收到所有信件，且 $T$ 尽可能小。允许邮局在开放前就收到信件。假设每个邮局在开放后立即发送信件。

形式化地说，寻找最小的非负 $T$ 以及值 $o_i$，使得对于每个给定的 $m$ 个三元组 $(a_j, b_j, d_j)$，满足 $o_{a_j} + d_j \le o_{b_j} + T$。

输入格式

输入包含一个或多个测试用例。

每个测试用例的第一行包含两个整数：$n$（城市数量）和 $m$（直接邮政路径数量）（$1 \le n \le 1000, 0 \le m \le 2000$）。

每个测试用例的第二行包含 $n$ 个标记 $o_i$，其中 $o_i$ 要么是一个问号（“?”），表示第 $i$ 个邮局的开放时间未给定，需要你来确定；要么是一个整数（$-10^5 \le o_i \le 10^5$），表示第 $i$ 个邮局的开放时间已知，你不能更改它。

接下来的 $m$ 行包含直接邮政路径的描述，每行一行。每行包含三个整数：$a_j, b_j, d_j$，表示从城市 $a_j$ 到城市 $b_j$ 的直接邮政路径，投递时间为 $d_j$（$1 \le a_j, b_j \le n, a_j \neq b_j, 1 \le d_j \le 100$）。保证对于每一对城市 $(a, b)$，至多存在一条从 $a$ 到 $b$ 的直接邮政路径。

单个测试用例中所有 $n$ 的总和不超过 $1000$。单个测试用例中所有 $m$ 的总和不超过 $2000$。测试用例之间没有特殊的分隔符。

输出格式

对于每个测试用例，精确打印两行。

第一行打印最小可能的非负实数 $T$，第二行打印值 $o_1, o_2, \dots, o_n$。$o_i$ 的值必须在 $[-10^9, 10^9]$ 范围内。打印 $T$ 和 $o_i$ 时，绝对误差不超过 $10^{-4}$。

输入中 $o_i \neq \text{“?”}$ 的值不得更改。对于给定的 $m$ 个三元组 $(a_j, b_j, d_j)$，必须满足 $o_{a_j} + d_j \le o_{b_j} + T$。

样例

输入 1

2 1
5 7
1 2 3

输出 1

1
5 7

输入 2

2 2
? ?
1 2 3
2 1 1
3 0
? ? 3

输出 2

2
9 10
0
1 -1 3