### 问题描述 小明是一家物流公司的仓库管理员。这家公司目前有 $ n $ 个分仓库和一个主仓库。每个仓库之间都有路可以相互到达。现在，公司准备添加一个新的仓库，并打算建设 $ m $ 条连接新仓库的路。小明想要知道，在添加新仓库和新路径后，从主仓库到其他各个仓库的最短路径是否有更新。主仓库总是编号为 1。 你的任务是写一个程序，来帮助小明解决这个问题。 ### 输入格式 第一行包含一个整数 $ n $ ( $ 1 \leq n \leq 100 $ )，表示原有的分仓库数量。 接下来的 $ n \times n $ 行，每行包含 $ n $ 个整数，构成一个 $ n \times n $ 的邻接矩阵。矩阵中的第 $ (i, j) $ 个元素表示从第 $ i $ 个仓库到第 $ j $ 个仓库的距离 $x$ 。所有距离都是非负整数，并且不超过 $ 10^6 $ 。 接着是一个整数 $ m $ ( $ 1 \leq m \leq n $ )，表示新仓库与其他仓库的连接数。 接下来 $ m $ 行，每行包含两个整数 $ a $ 和 $ b $ ( $ 0 \leq a, b \leq 10^6 $ )，表示新仓库到第 $ a $ 个仓库的距离为 $ b $ 。 ### 输出格式 输出一行，包含 $ n $ 个整数，用空格分隔。第 $ i $ 个整数表示从主仓库到第 $ i $ 个仓库的最短路径长度是否有更新。如果有更新，输出新的最短路径长度；如果没有更新，输出原来的最短路径长度。不包含新加的仓库的最短路。 ### 样例输入 ``` 3 0 1 3 1 0 2 3 2 0 2 1 1 3 1 ``` ### 样例输出 ``` 0 1 2 ``` ### 评测数据范围 $ 1 \leq n \leq 100 $，$ 0 \leq m \leq n $，$ 0 \leq x \leq 10^6 $， $ 0 \leq a, b \leq 10^6 $。