Shortest Travel Time

You are given a directed weighted graph representing travel times between cities. Your task is to answer a series of queries regarding the shortest travel time from a starting city to a destination city. If there is no route between the two cities, return \( -1 \).

For each test case, you are provided with:

• The number of cities \(N\), roads \(M\), and queries \(Q\).
• \(M\) road descriptions, where each road is given by three integers \(u\), \(v\), and \(w\) representing a one-way road from city \(u\) to city \(v\) with travel time \(w\).
• \(Q\) queries, where each query consists of two integers \(S\) and \(D\) asking for the shortest travel time from city \(S\) to city \(D\).</p>

  You are encouraged to implement your solution using Dijkstra's algorithm, where the recurrence is given by:

  [ dist[v] = \min{ dist[v],; dist[u] + w } ]

  If \(dist[D]\) remains infinite, output \( -1 \). Otherwise, output the computed \(dist[D]\).

  inputFormat

  The input is read from stdin and is structured as follows:

  1. An integer \(T\), the number of test cases.
  2. For each test case:
     1. A line with three space-separated integers \(N\) \(M\) \(Q\): the number of cities, roads, and queries respectively.
     2. \(M\) lines follow, each containing three integers \(u\), \(v\), and \(w\) representing a directed road from city \(u\) to city \(v\) with travel time \(w\).
     3. \(Q\) lines follow, each containing two integers \(S\) and \(D\) representing a query from city \(S\) to city \(D\).

  outputFormat

  For each query across all test cases, output a single integer on a new line indicating the shortest travel time from city \(S\) to city \(D\). If there is no path, output \( -1 \).

  ## sample

  3
  4 4 2
  1 2 5
  2 3 3
  3 4 1
  1 3 10
  1 4
  2 4
  4 3 1
  1 2 5
  2 3 3
  1 3 10
  3 4
  3 3 1
  1 2 2
  2 3 4
  1 3 7
  1 3
  

  9
  4
  -1
  6

  </p>