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.

Sample Input: 7 7 (n, m) 1 2 following m edges 1 4 2 3 3 6 4 5 5 6 6 7 3 q 7 3 1 (u, d, c) 5 1 2 5 0 3

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.