{"problem":{"name":"Restoring Road Network","description":{"content":"In Takahashi Kingdom, which once existed, there are $N$ cities, and some pairs of cities are connected bidirectionally by roads. The following are known about the road network: *   People traveled be","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc083_b"},"statements":[{"statement_type":"Markdown","content":"In Takahashi Kingdom, which once existed, there are $N$ cities, and some pairs of cities are connected bidirectionally by roads. The following are known about the road network:\n\n*   People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.\n*   Different roads may have had different lengths, but all the lengths were positive integers.\n\nSnuke the archeologist found a table with $N$ rows and $N$ columns, $A$, in the ruin of Takahashi Kingdom. He thought that it represented the shortest distances between the cities along the roads in the kingdom.\nDetermine whether there exists a road network such that for each $u$ and $v$, the integer $A_{u, v}$ at the $u$\\-th row and $v$\\-th column of $A$ is equal to the length of the shortest path from City $u$ to City $v$. If such a network exist, find the shortest possible total length of the roads.\n\n## Constraints\n\n*   $1 \\leq N \\leq 300$\n*   If $i ≠ j$, $1 \\leq A_{i, j} = A_{j, i} \\leq 10^9$.\n*   $A_{i, i} = 0$\n\n## Inputs\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_{1, 1}$ $A_{1, 2}$ $...$ $A_{1, N}$\n$A_{2, 1}$ $A_{2, 2}$ $...$ $A_{2, N}$\n$...$\n$A_{N, 1}$ $A_{N, 2}$ $...$ $A_{N, N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc083_b","tags":[],"sample_group":[["3\n0 1 3\n1 0 2\n3 2 0","3\n\nThe network below satisfies the condition:\n\n*   City $1$ and City $2$ is connected by a road of length $1$.\n*   City $2$ and City $3$ is connected by a road of length $2$.\n*   City $3$ and City $1$ is not connected by a road."],["3\n0 1 3\n1 0 1\n3 1 0","\\-1\n\nAs there is a path of length $1$ from City $1$ to City $2$ and City $2$ to City $3$, there is a path of length $2$ from City $1$ to City $3$. However, according to the table, the shortest distance between City $1$ and City $3$ must be $3$.\nThus, we conclude that there exists no network that satisfies the condition."],["5\n0 21 18 11 28\n21 0 13 10 26\n18 13 0 23 13\n11 10 23 0 17\n28 26 13 17 0","82"],["3\n0 1000000000 1000000000\n1000000000 0 1000000000\n1000000000 1000000000 0","3000000000"]],"created_at":"2026-03-03 11:01:13"}}