문제 설명

당신은 어떤 RPG 게임의 주인공입니다. 게임에는 n개의 도시(0번, 1번, ..., n-1번)와 m개의 도시 간 도로, 그리고 상수값 z가 있습니다. 각 도로는 일방통행이며, 도로마다 다른 가중치값 w (이 w는 z보다 항상 작습니다)를 가지고 있습니다.

당신은 게임 도중 매 턴당 다음 행동 중 하나를 취할 수 있습니다.

  1. 현재 있는 도시에서 연결된 도로를 따라 다른 도시로 이동합니다. 해당 도로의 가중치값을 w라고 할 때, w원을 얻습니다.
  2. 현재 있는 도시에서 움직이지 않고 z원을 얻습니다.
  3. 원하는 아무 도시로 순간 이동합니다. 이때 얻는 돈은 없습니다.

여기서 주의해야 할 점은, 같은 도로를 몇 번을 사용하든 그 도로를 사용할 때마다 얻는 금액은 동일하다는 것입니다.

이때, 당신에게 q개의 쿼리가 주어집니다. 각 쿼리는 단일 숫자 c로 이루어져 있으며, 당신은 이 게임을 0번 도시에서 0원을 가진 상태에서 시작했을 때, 정확히 c원을 얻는 것이 가능한지, 가능하다면 최소 몇 턴만에 c원을 얻을 수 있는지를 판별해야 합니다.

도시의 숫자 n, 게임의 상수값 z, 도시 간 도로의 정보 roads, 그리고 쿼리들로 이루어진 배열 queries가 매개변수로 주어집니다. 주어진 정보들을 활용하여 각 쿼리의 답(불가능한 경우 -1)을 배열에 담아 return 하도록 solution 함수를 완성해주세요.


제한사항
  • n은 2 이상 3,000 이하입니다.
  • z는 2 이상 50 이하입니다.
  • roads의 길이는 1 이상 3,000 이하입니다.
    • roads의 각 행은 [u, v, w] 3개의 정수로 이루어져 있으며, 이는 u번 도시부터 v번 도시까지 도로가 연결되어 있고, 해당 도로를 따라 이동했을 때 w원을 얻을 수 있음을 의미합니다.
    • 0 ≤ u, v < n 입니다.
    • 1 ≤ w < z 입니다.
    • u와 v는 서로 다른 수입니다.
    • u번 도시에서 v번 도시로 가는 도로는 최대 하나뿐입니다.
  • queries의 길이는 1 이상 100,000 이하입니다.
    • queries의 모든 숫자는 0 이상 1018 이하입니다.

입출력 예
n z roads queries result
5 5 [[1,2,3],[0,3,2]] [0,1,2,3,4,5,6] [0,-1,1,2,3,1,4]

입출력 예 설명

입출력 예 #1

  • 게임에 도시가 5개, z = 5, 그리고 도로가 2개 있습니다.
  • 다음 그림은 각 쿼리 별로 가장 빠르게 해당 금액을 정확히 획득하는 법을 도식화한 것입니다. rpg_millionaire_example.png
  • 0원은 시작할 때부터 가지고 있으므로, 답은 0입니다.
  • 1원을 가지는 것은 불가능하므로, 답은 -1입니다.
  • 2원을 가지기 위해서는 0번 도시에서 3번 도시로 도로를 타고 이동하면 가장 빠르므로, 답은 1입니다.
  • 3원을 가지기 위해서는 0번 도시에서 1번 도시로 순간 이동한 뒤, 2번 도시로 도로를 타고 이동하면 가장 빠르므로, 답은 2입니다.
  • 4원을 가지기 위해서는 0번 도시에서 3번 도시로 도로를 타고 이동하고, 다시 0번 도시로 순간 이동해서 똑같은 도로를 다시 사용하면 가장 빠르므로, 답은 3입니다.
  • 5원을 가지기 위해서는 0번 도시에서 가만히 있으면(2번째 행동) 가장 빠르므로, 답은 1입니다.
  • 6원을 가지기 위해서는 1번 도시로 순간이동하고, 2번 도시로 도로를 타고 이동하고, 다시 1번 도시로 순간 이동해서 똑같은 도로를 다시 사용하면 가장 빠르므로, 답은 4입니다.
  • 따라서, [0,-1,1,2,3,1,4] 를 return 해야 합니다.
실행 결과 실행 중지