### 问题描述 放假了，小蓝打算出去旅游，一共有 $n$ 个城市，$m$ 条道路，第 $i$ 条道路可以从城市 $u_i$ 到城市 $v_i$，也可以从城市 $v_i$ 到 $u_i$，所花费的时间为 $t_i$ （城市与城市之间最多有一条道路，且不存在同一个城市到自己的道路）。小蓝的家位于 $1$ 号城市，他可以使用 $k$ 次魔法，第 $i$ 次使用可以在家到城市 $x_i$ 之间建立一条道路（使用魔法无需花费时间），走这样的道路花费时间为 $w_i$。小蓝想知道从家出发前往每个城市的最短时间分别是多少（每个城市独立计算最短时间）。 ### 输入格式 第一行包含三个整数 $n,m$，分别表示城市数，道路数。 接下来 $m$ 行每行包含三个整数 $u_i,v_i,t_i$，分别表示每条道路的两个顶点，以及走这条道路需要花费的时间。 接下来一行包含一个整数 $k$，表示魔法数。 接下来 $k$ 行每行包含两个整数 $x_i,w_i$，分别表示使用魔法建立的道路所到达的城市，以及走这条道路需花费的时间。保证 $x_i$ 互不相同，并且不与之前已经有的边相同。 ### 输出格式 输出共 $n$ 行，每行包含一个整数，第 $i$ 行输出 $1$ 号城市到 $i$ 号城市所需的最短时间。若无法到达该城市请输出一行一个整数 `-1` 。 ### 样例输入 ```text 6 7 1 2 0 1 3 0 3 4 100000 3 5 100000 2 4 100000 2 5 100000 4 5 100000 1 4 1000 ``` ### 样例输出 ```text 0 0 0 1000 100000 -1 ``` ### 评测数据规模 对于所有评测数据，$ 2 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5, t_i = 0 \texttt{ 或 } 1 \times 10^5, 0 \leq w_i \leq 1 \times 10^5 $。