19330번 - Berland Post 스페셜 저지다국어

문제

Berland Post is the national postal service of Berland. There is exactly one post office in each of $n$ Berland cities. Cities and their respective offices are numbered by integers from 1ドル$ to $n$.

There are $m$ pairs of cities $(a, b)$ such that there is direct post traffic from $a$ to $b$. For each such pair of cities, the delivery time is known: formally, you are given $m$ triples $(a_j, b_j, d_j)$ meaning that each day, the post office in $a_j$ has to send correspondence to the post office in $b_j,ドル and $d_j$ is the time elapsed between sending the correspondence from $a_j$ and receiving it at $b_j$.

Each day, all offices must be open for the equal consecutive amount of time, which is denoted as $T$. But opening times may differ. If the opening time of $i$-th office is $o_i,ドル then the closing time is $o_i + T$.

Some values of $o_i$ are known and fixed, but some of them are up to you. Your goal is to find such values $T \ge 0$ and $o_i$ that each office receives all the correspondence no later than at closing time, and $T$ is the minimum possible. It is allowed for an office to receive the correspondence even before opening. Assume that each office sends the correspondence instantly after opening.

Formally, find the minimum possible non-negative $T$ and values $o_i$ such that $o_{a_j} + d_j \le o_{b_j} + T$ for each of the $m$ given triples $(a_j, b_j, d_j)$.

입력

The input contains one or more test cases.

Each test case starts with a line containing two integers: $n,ドル the number of cities, and $m,ドル the number of direct traffic paths (1ドル \le n \le 1000, 0 \le m \le 2000$).

The second line of each test case contains $n$ tokens $o_i,ドル where $o_i$ is either a question mark ("?") if the opening time of the office $i$ is not given and your task is to define it, or an integer ($-10^5 \le o_i \le 10^5$) if the opening time of the office $i$ is known and you can not change it.

The following $m$ lines contain descriptions of direct traffic paths, one per line. Each line contains three integers: $a_j,ドル $b_j,ドル and $d_j,ドル denoting direct post traffic from the city $a_j$ to the city $b_j$ with delivery time $d_j$ (1ドル \le a_j, b_j \le n,ドル $a_j \ne b_j,ドル 1ドル \le d_j \le 100$). It is guaranteed that, for each pair of the cities $(a, b),ドル there is at most one direct traffic path from $a$ to $b$.

The sum of all values $n$ in a test case does not exceed 1000ドル$. The sum of all values $m$ in a test case does not exceed 2000ドル$. The test cases just follow one another without any special separators.

출력

For each test case, print exactly two lines.

Print the minimum possible non-negative real value of $T$ on the first line and the values $o_1,ドル $o_2,ドル $\ldots,ドル $o_n$ on the second line. The values of $o_i$ must be in the range $[-10^9, 10^9]$. Print $T$ and $o_i$ with absolute error of at most 10ドル^{-4}$.

The values $o_i \ne $"?" in the input must not change. For each of the $m$ given triples $(a_j, b_j, d_j),ドル it must be true that $o_{a_j} + d_j \le o_{b_j} + T$.

제한

힌트