Scanf.scanf "%d %d" @@ fun n m ->
  let es = Array.init m (fun _ -> Scanf.scanf " %d %d" @@ fun a b -> a-1, b-1) in
  Scanf.scanf " %d" @@ fun q ->

  let qa = Array.init 11 (fun _ -> []) in
  for i = 0 to q-1 do
    Scanf.scanf " %d %d %d" @@ fun v d c ->
    qa.(10-d) <- (i, v-1, c) :: qa.(10-d)
  done;
  Array.iteri (fun i s -> qa.(i) <- List.rev s) qa;

  let cl = Array.make n (0, 0, 0) in
  qa.(0) |> List.iter (fun (i, v, c) -> cl.(v) <- i, c, 0);
  for r = 1 to 10 do
    Array.iter (fun (u, v) ->
      let iu, cu, ru = cl.(u) in
      let iv, cv, rv = cl.(v) in
      if ru < r then cl.(v) <- max cl.(v) (iu, cu, ru+1);
      if rv < r then cl.(u) <- max cl.(u) (iv, cv, rv+1);
    ) es;
    qa.(r) |> List.iter (fun (i, v, c) -> cl.(v) <- max cl.(v) (i, c, r));
  done;

  Array.iter (fun (_, v, _) -> Printf.printf "%d\n" v) cl