{"raw_statement":[{"iden":"problem statement","content":"There are $N$ rooms numbered $1$, $2$, $\\ldots$, $N$, each with one person living in it, and $M$ corridors connecting two different rooms. The $i$\\-th corridor connects room $U_i$ and room $V_i$ with a length of $W_i$.\nOne day (we call this day $0$), the $K$ people living in rooms $A_1, A_2, \\ldots, A_K$ got (newly) infected with a virus. Furthermore, on the $i$\\-th of the following $D$ days $(1\\leq i\\leq D)$, the infection spread as follows.\n\n> People who were infected at the end of the night of day $(i-1)$ remained infected at the end of the night of day $i$.  \n> For those who were not infected, they were newly infected if and only if they were living in a room within a distance of $X_i$ from at least one room where an infected person was living at the end of the night of day $(i-1)$. Here, the distance between rooms $P$ and $Q$ is defined as the minimum possible sum of the lengths of the corridors when moving from room $P$ to room $Q$ using only corridors. If it is impossible to move from room $P$ to room $Q$ using only corridors, the distance is set to $10^{100}$.\n\nFor each $i$ ($1\\leq i\\leq N$), print the day on which the person living in room $i$ was newly infected. If they were not infected by the end of the night of day $D$, print $-1$."},{"iden":"constraints","content":"*   $1 \\leq N\\leq 3\\times 10^5$\n*   $0 \\leq M\\leq 3\\times 10^5$\n*   $1 \\leq U_i < V_i\\leq N$\n*   All $(U_i,V_i)$ are different.\n*   $1\\leq W_i\\leq 10^9$\n*   $1 \\leq K\\leq N$\n*   $1\\leq A_1<A_2<\\cdots<A_K\\leq N$\n*   $1 \\leq D\\leq 3\\times 10^5$\n*   $1\\leq X_i\\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$U_1$ $V_1$ $W_1$\n$U_2$ $V_2$ $W_2$\n$\\vdots$\n$U_M$ $V_M$ $W_M$\n$K$\n$A_1$ $A_2$ $\\ldots$ $A_K$\n$D$\n$X_1$ $X_2$ $\\ldots$ $X_D$"},{"iden":"sample input 1","content":"4 4\n1 2 2\n2 3 1\n2 4 3\n3 4 2\n1\n1\n2\n3 3"},{"iden":"sample output 1","content":"0\n1\n1\n2\n\nThe infection spreads as follows.\n\n*   On the night of day $0$, the person living in room $1$ gets infected.\n*   The distances between room $1$ and rooms $2,3,4$ are $2,3,5$, respectively. Thus, since $X_1=3$, the people living in rooms $2$ and $3$ are newly infected on the night of day $1$.\n*   The distance between rooms $3$ and $4$ is $2$. Thus, since $X_2=3$, the person living in room $4$ also gets infected on the night of day $2$.\n\nTherefore, the people living in rooms $1,2,3,4$ were newly infected on days $0,1,1,2$, respectively, so print $0,1,1,2$ in this order on separate lines."},{"iden":"sample input 2","content":"7 7\n1 2 2\n2 3 3\n3 4 1\n4 5 1\n5 6 3\n3 7 1\n4 7 1\n2\n1 6\n2\n2 3"},{"iden":"sample output 2","content":"0\n1\n2\n-1\n2\n0\n-1"},{"iden":"sample input 3","content":"5 1\n1 2 5\n2\n1 3\n3\n3 7 5"},{"iden":"sample output 3","content":"0\n2\n0\n-1\n-1\n\nNote that it is not always possible to move between any two rooms using only corridors."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}