Given a connected graph with n nodes and m edges (n, m <= 1e5). There are q queries (q <= 1e5), each has type of (u, d, c) means to color all nodes which have the smallest distance to u <= d color c (d <= 10, c <= 1e5). What is the color of n nodes after q queries.

I can only do smaller subtask when n,m,q <= 2000 with bfs. I do think about solving queries backward and color nodes that are empty but still don't know how to optimize it. Can anyone help me. Thanks.