Given a directed weighted graph where weight indicates distance, for each query, determine the length of the shortest path between nodes.  There may be many queries, so efficiency counts.  

For example, your graph consists of $5$ nodes as in the following:

A few queries are from node $4$ to node $3$, node $2$ to node $5$, and node $5$ to node $3$. 

There are two paths from $4$ to $3$:

$4\Rightarrow1\Rightarrow2\Rightarrow3$ at a distance of $4+5+1=10$  
$4\Rightarrow1\Rightarrow5\Rightarrow3$ at a distance of $4+3+2=9$ 

In this case we choose path $2$.  

There is no path from $2$ to $5$, so we return $-1$.  

There is one path from $5$ to $3$:  

$5\Rightarrow3$ at a distance of $2$.  

Input Format

The first line has two integers $n$ and $m$, the number of nodes and the number of edges in the graph. 

Each of the next $m$ lines contains three space-separated integers $\mbox{u}$ $v$ and $\boldsymbol{w}$, the two nodes between which the directed edge $u\Rightarrow v$ exists, and $\boldsymbol{w}$, the length of the edge. 

The next line contains a single integer $\textit{q}$, the number of queries. 

Each of the next $\textit{q}$ lines contains two space-separated integers $a$ and $\boldsymbol{b}$, denoting the start and end nodes for traversal.  

Constraints

$2\leq n\leq400$ 

$1\leq m\leq\frac{n\times(n-1)}{2}$ 

$1\leq q\leq10^5$ 

$1\leq u,v\leq n$ 

$1\leq w\leq350$ 

The distance from a node to itself is always $0$ and it is always reachable from itself.

If there are edges between the same pair of nodes with different weights, the last one (most recent) is to be considered as the only edge between them.

Output Format

Print $\textit{q}$ lines, each containing a single integer specifying the shortest distance for the query.  

If the destination node is not reachable, return $-1$.  

Sample Input
STDIN   Function
-----   --------
4 5     n = 4, m = 5
1 2 5   u = 1, v = 2, w = 5
1 4 24  u = 1, v =4, w = 24 ...
2 4 6
3 4 4
3 2 7
3       q = 3
1 2     query 0: from 1 to 2
3 1     query 1: from 3 to 1
1 4     query 2: from 1 to 4

Sample Output
5
-1
11

Explanation

The graph given in the test case is:

The shortest paths for the 3 queries are :

$1\Rightarrow2$: The direct path is shortest with weight 5  
$-1$: There is no way of reaching node 1 from node 3  
$1\Rightarrow2\Rightarrow4$: The indirect path is shortest with weight (5+6) = 11 units. The direct path is longer with 24 units length.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
INFINITY = 4294967295

class vertex:

	def __init__(self):
		self.adj = {}

def bellman_ford(V, s, sp):
	sp[s][s] = 0
	sps = sp[s]
	for i in range(0, len(V)):
		done = True
		for x in range(0, len(V)):
			for y in V[x].adj.keys():
				w = V[x].adj[y]
				if sps[y] > sps[x] + w:
					sps[y] = sps[x] + w
					done = False
		if done == True:
			break
var = input().split()
(N, M) = (int(var[0]), int(var[1]))
SP_done = [INFINITY] * N
V = []
V = [vertex() for i in range(0, N)]
SP = [[INFINITY for i in range(0, N)] for i in range(0, N)]
for i in range(0, M):
	var = input().split()
	(x, y, w) = (int(var[0]), int(var[1]), int(var[2]))
	x = x - 1
	y = y - 1
	V[x].adj[y] = w
T = int(input())
out = ''
for t in range(0, T):
	var = input().split()
	(x, y) = (int(var[0]), int(var[1]))
	x = x - 1
	y = y - 1
	if SP_done[x] != 0:
		SP_done[x] = 0
		bellman_ford(V, x, SP)
	if SP[x][y] == INFINITY:
		out += '{}\n'.format(-1)
	else:
		out += '{}\n'.format(SP[x][y])
print(out)


import sys
INFINITY = sys.maxsize

def main():
	(n, m) = [int(value) for value in input().split()]
	graph = dict()
	for i in range(1, n + 1):
		graph[i] = set()
	lengths = dict()
	for _ in range(m):
		(x, y, r) = [int(value) for value in input().split()]
		graph[x].add(y)
		lengths[x, y] = r
	q = int(input())
	queries = dict()
	queryOrder = []
	shortestDistances = dict()
	for _ in range(q):
		(source, target) = [int(value) for value in input().split()]
		if source not in queries:
			queries[source] = set()
		queries[source].add(target)
		queryOrder.append((source, target))
	for (source, targets) in queries.items():
		shortestDistance = dijkstra(graph, source, lengths, targets)
		shortestDistances[source] = shortestDistance
	for (querySource, queryTarget) in queryOrder:
		print(str(shortestDistances[querySource][queryTarget]))

def dijkstra(graph, source, lengths, targets):
	distance = dict()
	previous = dict()
	shortestDistance = dict()
	vertexSet = set()
	for (key, _) in graph.items():
		if key != source:
			distance[key] = INFINITY
			previous[key] = -1
		vertexSet.add(key)
	distance[source] = 0
	previous[source] = -1
	while vertexSet:
		minVertex = -1
		minDistance = INFINITY
		for vertex in vertexSet:
			if distance[vertex] < minDistance:
				minVertex = vertex
				minDistance = distance[vertex]
		if minVertex == -1:
			if len(shortestDistance) < len(targets):
				for target in targets:
					if target not in shortestDistance:
						shortestDistance[target] = -1
			break
		if minVertex in targets:
			if minDistance == INFINITY:
				shortestDistance[minVertex] = -1
			else:
				shortestDistance[minVertex] = minDistance
			if len(shortestDistance) == len(targets):
				break
		vertexSet.remove(minVertex)
		for neighbor in graph[minVertex]:
			alternate = distance[minVertex] + lengths[minVertex, neighbor]
			if alternate < distance[neighbor]:
				distance[neighbor] = alternate
				previous[neighbor] = minVertex
	return shortestDistance
main()


graph = {}

def build_graph(x, y, d):
	if x in graph:
		graph[x].append(y)
	else:
		graph[x] = [y]
	graph[x, y] = d
shortest = {}

def query_graph(x, y):
	if x == y:
		return 0
	if not (x, y) in shortest:
		shortest[x, y] = path(x, y)
	return shortest[x, y]
import heapq

def path(x, y):
	heap = []
	heapq.heappush(heap, (0, x))
	visited = {}
	while heap:
		(distance, current) = heapq.heappop(heap)
		if not current in visited:
			visited[current] = 1
			if current == y:
				return distance
			if current in graph:
				for n in graph[current]:
					heapq.heappush(heap, (distance + graph[current, n], n))
	return -1
import sys
state = n = m = counter = 0
out = []
for line in sys.stdin:
	if state == 0:
		(_, m) = [int(e) for e in line.strip().split(' ') if e.strip() != '']
		state = 1
	elif state == 1:
		(x, y, d) = [int(e) for e in line.strip().split(' ') if e.strip() != '']
		build_graph(x, y, d)
		counter += 1
		if counter == m:
			state = 2
			counter = 0
	elif state == 2:
		n = int(line.strip())
		state = 3
	elif state == 3:
		(x, y) = [int(e) for e in line.strip().split(' ') if e.strip() != '']
		out.append(query_graph(x, y))
		counter += 1
		if counter == n:
			for o in out:
				print(o)


from sys import stdin
from collections import defaultdict
import heapq
(n, m) = (int(x) for x in stdin.readline().split())
adj = defaultdict(dict)
for mi in range(m):
	(x, y, r) = (int(z) for z in stdin.readline().split())
	adj[x][y] = r
q = int(stdin.readline().strip())
dists = {}
heap = {}
for ni in range(1, n + 1):
	dists[ni] = {}
	heap[ni] = [(0, ni)]
for qi in range(q):
	(a, b) = (int(x) for x in stdin.readline().split())
	while b not in dists[a]:
		if not heap[a]:
			dists[a][b] = -1
			break
		(dv, v) = heapq.heappop(heap[a])
		if v not in dists[a]:
			dists[a][v] = dv
			for (y, dy) in adj[v].items():
				heapq.heappush(heap[a], (dv + dy, y))
	print(dists[a][b])


import sys

def main():
	(distance_matrix, node_count) = read_test_case()
	floyd_marshall(distance_matrix, node_count)
	queries = read_in_queries()
	for (first, second) in queries:
		value = distance_matrix[first - 1][second - 1]
		if value == sys.maxsize:
			print(-1)
		else:
			print(value)

def read_test_case():
	line = input()
	node_count = line.split()[0]
	edge_count = line.split()[1]
	distance_matrix = initialize_distance_matrix(int(node_count))
	for edge in range(int(edge_count)):
		new_edge = input()
		(first_node, second_node, distance) = new_edge.split()
		distance_matrix[int(first_node) - 1][int(second_node) - 1] = int(distance)
	return (distance_matrix, int(node_count))

def read_in_queries():
	query_count = int(input())
	queries = []
	for _ in range(query_count):
		(first, second) = input().split()
		queries.append((int(first), int(second)))
	return queries

def initialize_distance_matrix(node_count):
	matrix = [[sys.maxsize for y in range(node_count)] for x in range(node_count)]
	for node in range(node_count):
		matrix[node][node] = 0
	return matrix

def floyd_marshall(distance_matrix, node_count):
	for stop in range(node_count):
		iterate_with_stop(distance_matrix, stop)
	return distance_matrix

def iterate_with_stop(distance_matrix, stop):
	distances_from_stop = distance_matrix[stop]
	for (idx1, distances) in enumerate(distance_matrix):
		distance_to_stop = distances[stop]
		for (idx2, dist) in enumerate(distances):
			distance_with_stop = distance_to_stop + distances_from_stop[idx2]
			if dist > distance_with_stop:
				distance_matrix[idx1][idx2] = distance_with_stop
	return distance_matrix
main()


from heapq import heappush, heappop

def dijkstra(s, G, E):
	dist = [-1] * (len(G) + 1)
	dist[s] = 0
	queue = [(0, s)]
	seen = set()
	while queue:
		(_, u) = heappop(queue)
		if u in seen:
			continue
		seen.add(u)
		for v in G[u]:
			edge_weight = E[u, v]
			if dist[v] == -1 or dist[v] > dist[u] + edge_weight:
				dist[v] = dist[u] + edge_weight
			heappush(queue, (dist[v], v))
	return dist
(N, M) = map(int, input().split())
G = {k: [] for k in range(1, N + 1)}
E = {}
for _ in range(M):
	(u, v, r) = map(int, input().split())
	G[u].append(v)
	E[u, v] = r
dists = [None]
for v in range(1, N + 1):
	dists.append(dijkstra(v, G, E))
Q = int(input())
for _ in range(Q):
	(u, v) = map(int, input().split())
	print(dists[u][v])


import heapq
(n, m) = map(int, input().strip().split(' '))
edges = (tuple(map(int, input().strip().split(' '))) for _ in range(m))
graph = [dict() for _ in range(n)]
for (x, y, r) in edges:
	graph[x - 1][y - 1] = r
q = int(input().strip())
qs = (tuple(map(int, input().strip().split(' '))) for _ in range(q))
infinite = float('inf')
cache = {}
for (a, b) in qs:
	if (a - 1, b - 1) in cache:
		print(cache[a - 1, b - 1])
		continue
	source = a - 1
	distances = {source: 0}
	visited = set()
	heap = []
	heapq.heappush(heap, (0, source))
	while heap:
		(dist, current) = heapq.heappop(heap)
		if current == b - 1:
			break
		if current in visited:
			continue
		visited.add(current)
		for (neighbor, r) in graph[current].items():
			dist_tmp = dist + r
			if dist_tmp < distances.get(neighbor, infinite):
				distances[neighbor] = dist_tmp
				heapq.heappush(heap, (dist_tmp, neighbor))
	cache[a - 1, b - 1] = distances.get(b - 1, -1)
	print(cache[a - 1, b - 1])


from heapq import heappush, heappop
INF_ = 10 ** 15

def dijkstra(graph, edges, S, E, N):
	weights = dict(zip(range(1, N + 1), [-1] * N))
	weights[S] = 0
	seen = set()
	queue = [(weights[S], S)]
	while queue:
		(_, u) = heappop(queue)
		if u in seen:
			continue
		seen.add(u)
		for node in graph[u]:
			edge = edges[u, node]
			if weights[node] == -1 or weights[node] > weights[u] + edge:
				weights[node] = weights[u] + edge
			heappush(queue, (weights[node], node))
	res = [-1 if weights.get(e, INF_) == INF_ else weights.get(e, INF_) for e in E]
	return res
(N, M) = map(int, input().split())
graph = {k: [] for k in range(1, N + 1)}
edges = {}
for _ in range(M):
	(x, y, r) = map(int, input().split())
	graph[x].append(y)
	edges[x, y] = r
Q = int(input())
queris = {u: [] for u in range(1, N + 1)}
ordered_queries = []
query_res = {}
for _ in range(Q):
	(u, v) = map(int, input().split())
	ordered_queries.append((u, v))
	queris[u].append(v)
for k in queris:
	if len(queris[k]) > 0:
		res = dijkstra(graph, edges, k, queris[k], N)
		for (v, r) in zip(queris[k], res):
			query_res[k, v] = r
for q in ordered_queries:
	print(query_res[q])


import heapq
from pprint import pprint

def dijkstra(G, s):
	dist = {k: float('inf') for k in G}
	pq = [(0, s)]
	while pq:
		(c, u) = heapq.heappop(pq)
		if c <= dist[u]:
			dist[u] = c
			for v in G[u]:
				if dist[u] + G[u][v] < dist[v]:
					heapq.heappush(pq, (dist[u] + G[u][v], v))
					dist[v] = dist[u] + G[u][v]
	return dist
(N, M) = [int(x) for x in input().split()]
G = {k: {} for k in range(1, N + 1)}
for m in range(M):
	(x, y, r) = [int(x) for x in input().split()]
	G[x][y] = r
Q = [[int(x) for x in input().split()] for _ in range(int(input()))]
D = {s: dijkstra(G, s) for s in G}
for (x, y) in Q:
	print(D[x][y] if D[x][y] < float('inf') else -1)


import math

def printv(v):
	if v >= 1000000000:
		print(-1)
	else:
		print(v)
(n, m) = map(int, input().split())
adj = []
cost = []
dist = [1000000000] * n
g = set()
a = []
con = set()
for i in range(n):
	adj.append([])
	cost.append([1000000000] * n)
	cost[i][i] = 0
	g.add(i)
	a.append([1000000000] * n)
for c in range(m):
	(x, y, r) = map(int, input().split())
	adj[x - 1].append(y - 1)
	cost[x - 1][y - 1] = r
q = int(input())
for _ in range(q):
	(s, f) = map(int, input().split())
	s = s - 1
	f = f - 1
	if s in con:
		printv(a[s][f])
	else:
		S = {s}
		con.add(s)
		for i in range(0, n):
			dist[i] = cost[s][i]
		for k in range(1, n):
			mi = 1000000000
			for u in g - S:
				if dist[u] <= mi:
					mi = dist[u]
					m = u
			S.add(m)
			for w in adj[m]:
				if w not in S:
					if dist[w] > dist[m] + cost[m][w]:
						dist[w] = dist[m] + cost[m][w]
		for i in range(n):
			a[s][i] = dist[i]
		printv(a[s][f])


import heapq
from collections import defaultdict
graph = defaultdict(dict)
cache = {}

def memo(f):

	def wrapper(*args):
		if args not in cache:
			cache[args] = f(*args)
		return cache[args]
	return wrapper

@memo
def dist(a, b):
	seen = set()
	pq = []
	heapq.heappush(pq, (0, a))
	while pq:
		(acc_w, cur_v) = heapq.heappop(pq)
		if cur_v == b:
			return acc_w
		if cur_v not in seen:
			seen.add(cur_v)
			for next_v in graph[cur_v]:
				if next_v not in seen:
					next_w = graph[cur_v][next_v]
					heapq.heappush(pq, (next_w + acc_w, next_v))
	return -1

def add_edge(a, b, weight):
	graph[a][b] = weight
(num_nodes, num_edges) = (int(s) for s in input().strip().split())
for _ in range(num_edges):
	(a, b, weight) = (int(s) for s in input().strip().split())
	add_edge(a, b, weight)
q = int(input())
for _ in range(q):
	(a, b) = (int(s) for s in input().strip().split())
	print(dist(a, b))


from collections import defaultdict
input_fn = input
inf = float('inf')

def get_int():
	return int(input_fn())

def get_int_list():
	return [int(i) for i in input_fn().split()]

def floyd_list(vs, edges):
	vs2 = [0] + list(vs)
	dist = [[inf for i in vs2] for j in vs2]
	for (v1, v2, c) in edges:
		dist[v1][v2] = c
	for v in vs:
		dist[v][v] = 0
	for k in vs:
		row_k = dist[k]
		for i in vs:
			row_i = dist[i]
			ele_i_k = row_i[k]
			if ele_i_k is inf:
				continue
			for j in vs:
				ele_k_j = row_k[j]
				if ele_k_j is inf:
					continue
				d = ele_i_k + ele_k_j
				if d < row_i[j]:
					row_i[j] = d
	return dist

def solve(edges, ques, v, e):
	vs = range(1, v + 1)
	dist = floyd_list(vs, edges)
	ans = [dist[i][j] for (i, j) in ques]
	ans = ['-1' if d is inf else str(d) for d in ans]
	print(*ans, sep='\n')

def main():
	(v, e) = get_int_list()
	edges = [get_int_list() for _ in range(e)]
	ques = [get_int_list() for _ in range(get_int())]
	solve(edges, ques, v, e)
main()


import sys
known_nodes = {}

class Node:

	def __init__(self, index):
		self.index = index
		self.edges = {}

	def add_edge(self, other_index, distance):
		self.edges[other_index] = distance

def create_models_from_input():
	line = input()
	(nodes, edges) = line.split()
	nodes = int(nodes)
	edges = int(edges)
	for i in range(1, nodes + 1):
		known_nodes[i] = Node(i)
	for i in range(edges):
		line = input()
		(n1, n2, dist) = line.split()
		n1 = int(n1)
		n2 = int(n2)
		dist = int(dist)
		known_nodes[n1].add_edge(n2, dist)

def minimum_distance(distances, Q):
	smallest_distance = sys.maxsize
	smallest_node = None
	for v in Q:
		if distances[v] <= smallest_distance:
			smallest_distance = distances[v]
			smallest_node = v
	return smallest_node

def djikstra(source_index):
	dist = {}
	prev = {}
	unprocessed = []
	for (k, v) in known_nodes.items():
		dist[v] = sys.maxsize
		prev[v] = None
		unprocessed.append(v)
	dist[known_nodes[source_index]] = 0
	while len(unprocessed) > 0:
		u = minimum_distance(dist, unprocessed)
		unprocessed.remove(u)
		for (v_index, v_distance) in u.edges.items():
			v = known_nodes[v_index]
			alt = dist[u] + v_distance
			if alt < dist[v]:
				dist[v] = alt
				prev[v] = u
	return (dist, prev)

def print_distances_from_input():
	queries = []
	num_queries = int(input())
	for i in range(num_queries):
		line = input()
		(start, end) = line.split()
		start = int(start)
		end = int(end)
		queries.append((start, end))
	known_answers = {}
	for q in queries:
		(start, end) = q
		if start in known_answers.keys():
			(dist, prev) = known_answers[start]
		else:
			(dist, prev) = djikstra(start)
			known_answers[start] = (dist, prev)
		distance_from_source = dist[known_nodes[end]]
		print(distance_from_source if distance_from_source < sys.maxsize else -1)
create_models_from_input()
print_distances_from_input()


import collections
Edge = collections.namedtuple('Edge', 'node weight')

class Node:

	def __init__(self, node_id):
		self.id = node_id
		self.weight = None
		self.visited = False
		self.adj_dict = {}
		self.heap_location = None

	def update_heap(self, location):
		self.heap_location = location

	def __lt__(self, other):
		if other.weight == self.weight or self.weight is None:
			return False
		if other.weight is None:
			return True
		else:
			return self.weight < other.weight

	def set_origin(self):
		self.weight = 0
		self.visited = True
		self.heap_location = None

	def add_adj(self, edge: Edge):
		self.adj_dict[edge.node.id] = edge

	def __str__(self):
		return '%s %s %s %s' % (self.id, self.weight, self.visited, self.heap_location)

	def get_weight(self):
		if self.weight is None:
			return -1
		else:
			return self.weight

	def reset(self):
		self.visited = False
		self.weight = None

class Graph:

	def __init__(self, node_count, edge_list: list):
		self.my_dict = {}
		self.min_heap = None
		self.origin = None
		for i in range(1, node_count + 1):
			my_node = Node(i)
			self.my_dict[i] = my_node
		for edge in edge_list:
			node1 = self.my_dict[edge[0]]
			node2 = self.my_dict[edge[1]]
			node1.add_adj(Edge(node2, edge[2]))

	def set_origin(self, origin):
		self.origin = origin
		self.my_dict[origin].reset()
		self.my_dict[origin].weight = 0
		self.min_heap = MinHeap()
		for node_id in self.my_dict.keys():
			if node_id != origin:
				self.my_dict[node_id].reset()
			self.min_heap.add(self.my_dict[node_id])

	def should_continue(self):
		return len(self.min_heap) > 0 and self.min_heap.query().weight is not None

	def get_min(self):
		return self.min_heap.extract()

	def relax(self, my_node, update_weight):
		if my_node.weight is None or update_weight < my_node.weight:
			my_node.weight = update_weight
			self.min_heap.bubble_up(my_node.heap_location)

	def __str__(self):
		result = ''
		for node_id in sorted(self.my_dict):
			if node_id != self.origin:
				result += str(self.my_dict[node_id].get_weight()) + ' '
		return result.strip()

	@property
	def weight_dict(self):
		weight = {}
		for node in self.my_dict.values():
			weight[node.id] = node.get_weight()
		return weight

class MinHeap:

	def __init__(self):
		self.min_heap = []

	def __len__(self):
		return len(self.min_heap)

	def add(self, value):
		self.min_heap.append(value)
		self.update_heap(len(self.min_heap) - 1)
		self.bubble_up(len(self.min_heap) - 1)

	def bubble_up(self, index):
		if index > 0:
			parent = self._get_parent(index)
			if self.min_heap[index] < self.min_heap[parent]:
				self._swap(index, parent)
				self.bubble_up(parent)

	def update_heap(self, location):
		self.min_heap[location].update_heap(location)

	def query(self):
		return self.min_heap[0]

	def extract(self):
		result = self.query()
		self.min_heap[0].update_heap(None)
		self.min_heap[0] = self.min_heap[len(self.min_heap) - 1]
		self.update_heap(0)
		del self.min_heap[len(self.min_heap) - 1]
		self._heapify(0)
		return result

	def _heapify(self, index):
		index_left = self._get_left(index)
		index_right = self._get_right(index)
		if index_left >= len(self.min_heap):
			return
		if index_right >= len(self.min_heap):
			index_child = index_left
		else:
			index_child = index_right if self.min_heap[index_right] < self.min_heap[index_left] else index_left
		if self.min_heap[index_child] < self.min_heap[index]:
			self._swap(index, index_child)
			self._heapify(index_child)

	def _swap(self, index1, index2):
		(self.min_heap[index1], self.min_heap[index2]) = (self.min_heap[index2], self.min_heap[index1])
		self.update_heap(index1)
		self.update_heap(index2)

	def _get_left(self, index):
		return (index + 1) * 2 - 1

	def _get_right(self, index):
		return self._get_left(index) + 1

	def _get_parent(self, index):
		return (index - 1) // 2

class Dijkstra:

	def __init__(self, node_count, edge_list: list):
		self.graph = Graph(node_count, edge_list)
		self.weight_dict = {}

	def calculate_weights(self, origin):
		self.graph.set_origin(origin)
		while self.graph.should_continue():
			current_node = self.graph.get_min()
			for edge in current_node.adj_dict.values():
				if not edge.node.visited:
					self.graph.relax(edge.node, current_node.weight + edge.weight)
			current_node.visited = True
		self.weight_dict[origin] = self.graph.weight_dict

	def calculate(self, origin, destination):
		if origin not in self.weight_dict:
			self.calculate_weights(origin)
		print(self.weight_dict[origin][destination])

def main():
	in_str = input()
	edge_list = []
	(nodes, edges) = get_int_list(in_str)
	for i in range(edges):
		edge_str = input()
		edge_list.append(get_int_list(edge_str))
	my_obj = Dijkstra(nodes, edge_list)
	case_str = input().strip()
	queries = int(case_str)
	for i in range(queries):
		(origin, destination) = get_int_list(input().strip())
		my_obj.calculate(origin, destination)

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


from collections import defaultdict
M = 10 ** 9
(n, m) = map(int, input().split())
edges = defaultdict(lambda : defaultdict(int))
outgoing = defaultdict(list)
for _ in range(m):
	(s, t, w) = map(int, input().split())
	edges[s][t] = w
	outgoing[s].append(t)

def dijkstra(distance, s, t):
	vertex_stack = []
	index_to_vertex = {}
	for j in range(1, n + 1):
		vertex = {}
		if s == j:
			vertex = {'index': j, 'dist': 0, 'prev': s}
		elif distance[s][j] == 0:
			vertex = {'index': j, 'dist': M, 'prev': None}
		else:
			vertex = {'index': j, 'dist': distance[s][j], 'prev': s}
		vertex_stack.append(vertex)
		index_to_vertex[j] = vertex
	target_vertex = None
	while vertex_stack:
		u = vertex_stack[0]
		for vertex in vertex_stack:
			if vertex['dist'] < u['dist']:
				u = vertex
		if u['index'] == t:
			target_vertex = u
			break
		else:
			vertex_stack.remove(u)
			for j in outgoing[u['index']]:
				v = index_to_vertex[j]
				alt = u['dist'] + edges[u['index']][v['index']]
				if alt < v['dist']:
					v['dist'] = alt
					v['prev'] = u['index']
	if target_vertex and target_vertex['prev']:
		distance[s][t] = target_vertex['dist']
		b = target_vertex
		while b['index'] != s:
			a = index_to_vertex[b['prev']]
			distance[s][a['index']] = a['dist']
			distance[a['index']][t] = target_vertex['dist'] - a['dist']
			b = a
	else:
		for vertex in index_to_vertex.values():
			if vertex['dist'] == M:
				distance[s][vertex['index']] = -1
			else:
				distance[s][vertex['index']] = vertex['dist']
	return distance
distance = defaultdict(lambda : defaultdict(int))
for _ in range(int(input())):
	(s, t) = map(int, input().split())
	if s == t:
		print(0)
	elif distance[s][t] == 0:
		distance = dijkstra(distance, s, t)
		print(distance[s][t])
	else:
		print(distance[s][t])


class graph:

	def __init__(self, n):
		self.nodes = {i: {} for i in range(1, n + 1)}

	def connect(self, start, end, l):
		self.nodes[start][end] = l

def djikstra(g, start):
	dist = {i: float('inf') for i in g.nodes}
	done = {i: False for i in g.nodes}
	dist[start] = 0
	que = [i for i in g.nodes]
	que.insert(0, que.pop(start - 1))
	while que:
		current = que.pop(0)
		for i in g.nodes[current]:
			if not done[i]:
				dist[i] = min(dist[i], dist[current] + g.nodes[current][i])
		done[current] = True
		try:
			ind = que.index(min(que, key=lambda x: dist[x]))
			que.insert(0, que.pop(ind))
		except Exception as e:
			break
	return dist
(n, m) = [int(i) for i in input().split()]
query = {}
g = graph(n)
for i in range(m):
	(x, y, r) = [int(i) for i in input().split()]
	g.connect(x, y, r)
for i in g.nodes:
	query[i] = djikstra(g, i)
for i in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	ans = query[a][b]
	if ans == float('inf'):
		ans = -1
	print(ans)


import sys
(N, M) = input().strip().split()
(N, M) = [int(N), int(M)]
edges = []
for m in range(M):
	edge = input().strip().split(' ')
	edge = list(map(int, edge))
	edges.append(edge)
Q = int(input().strip())
queries = []
for q in range(Q):
	query = input().strip().split(' ')
	query = list(map(int, query))
	queries.append(query)
graph = []
Inf = 1000000
for n in range(N):
	row = []
	for k in range(N):
		if k == n:
			row.append(0)
		else:
			row.append(Inf)
	graph.append(row)
for (node1, node2, distance) in edges:
	graph[node1 - 1][node2 - 1] = distance
import array

def Floyd(graph, N):
	for k in range(N):
		graphK = array.array('I', graph[k])
		for i in range(N):
			graphI = array.array('I', graph[i])
			graphIK = graphI[k]
			if graphIK == Inf:
				continue
			for j in range(N):
				length = graphIK + graphK[j]
				if graphI[j] > length:
					graph[i][j] = length
	return graph
graph = Floyd(graph, N)
for (node1, node2) in queries:
	ans = graph[node1 - 1][node2 - 1]
	if ans == Inf:
		ans = -1
	print(ans)


class Graph:

	def __init__(self, n, plusone=True):
		self.n = n
		self.edge_map = dict()
		for i in range(n):
			self.edge_map[i + 1 if plusone else i] = dict()

	def add_edges(self, edges, directed=False):
		self.edges = edges
		for edge in edges:
			self.edge_map[edge[0]][edge[1]] = edge[2]
			if not directed:
				self.edge_map[edge[1]][edge[0]] = edge[2]

	@classmethod
	def from_stdin(cls, n, m, directed, pipe):
		g = Graph(n)
		edges = list()
		for _ in range(m):
			(i, j, w) = [int(x) for x in pipe.readline().strip().split()]
			edges.append((i, j, w))
		g.add_edges(edges, directed)
		return g

	def dijkstra(self, s):
		shortest = dict()
		shortest[s] = 0
		reached = {s: 0}
		while len(reached) > 0:
			m_st = min(reached, key=lambda k: reached[k])
			m_di = reached.pop(m_st)
			shortest[m_st] = m_di
			for (ed, w) in self.edge_map[m_st].items():
				if ed in shortest:
					continue
				if ed not in reached or reached[ed] > m_di + w:
					reached[ed] = m_di + w
		for i in range(1, self.n + 1):
			if i not in shortest:
				shortest[i] = -1
		return shortest

	def dijkstra_cache(self):
		cache = dict()
		for st in self.edge_map.keys():
			path = dict()
			path[st] = 0
			cache[st] = path
		for st in self.edge_map.keys():
			shortest = cache[st]
			reached = cache[st].copy()
			while len(reached) > 0:
				m_st = min(reached, key=lambda k: reached[k])
				m_di = reached.pop(m_st)
				shortest[m_st] = m_di
				for (ed, w) in cache[m_st].items():
					if ed in shortest:
						continue
					if ed not in reached or reached[ed] > m_di + w:
						reached[ed] = m_di + w
				for (ed, w) in self.edge_map[m_st].items():
					if ed in shortest:
						continue
					if ed not in reached or reached[ed] > m_di + w:
						reached[ed] = m_di + w
		return cache

	def prim(self, s):
		v_new = {s}
		chosen_edges = list()
		while len(v_new) < self.n:
			min_edge = (-1, -1, float('inf'))
			for start in v_new:
				for (end, w) in self.edge_map[start].items():
					if end in v_new:
						continue
					if w < min_edge[2]:
						min_edge = (start, end, w)
			if min_edge[0] == -1:
				break
			chosen_edges.append(min_edge)
			v_new.add(min_edge[1])
		return chosen_edges

	def kruskal(self):
		g_new = list()
		edges = list()
		for i in self.edge_map.keys():
			g_new.append([i])
		edges_w = list()
		for (i, e) in enumerate(self.edges):
			edges_w.append((e[2], sum(e), i))
		edges_w = sorted(edges_w)
		while len(g_new) > 1 and len(edges_w) > 0:
			edge = self.edges[edges_w.pop(0)[2]]
			part_st = part_ed = -1
			for (i, part) in enumerate(g_new):
				if edge[0] in part:
					part_st = i
				if edge[1] in part:
					part_ed = i
				if part_st >= 0 and part_ed >= 0:
					break
			if part_st != part_ed:
				g_new[part_st] += g_new[part_ed]
				g_new.pop(part_ed)
				edges.append(edge)
		return edges
import sys
fin = sys.stdin
(n, m) = [int(x) for x in fin.readline().split()]
g = Graph.from_stdin(n, m, True, fin)
cache = g.dijkstra_cache()
q = int(fin.readline().strip())
for _ in range(q):
	(i, j) = [int(x) for x in fin.readline().strip().split()]
	if j in cache[i]:
		print(cache[i][j])
	else:
		print(-1)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().split()))
e = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(e[f]) if to == t))
		e[f][idx] = (t, r)
	except StopIteration:
		e[f].append((t, r))
q = [tuple((int(x) for x in input().split())) for _ in range(int(input()))]
(qd, a) = ({}, {})
for (fr, to) in q:
	if fr not in qd:
		qd[fr] = {to}
	else:
		qd[fr].add(to)
for (fr, tos) in qd.items():
	(v, d) = ({fr}, {node: -1 for node in range(1, n + 1)})
	d[fr] = 0
	while v:
		nv = set()
		for no in v:
			nd = d[no]
			for (n2, r) in e[no]:
				nw = nd + r
				if d[n2] == -1 or nw < d[n2]:
					d[n2] = nw
					nv.add(n2)
		v = nv
	for to in tos:
		a[fr, to] = d[to]
for (fr, to) in q:
	print(a[fr, to])


import sys

class Graphy:

	def __init__(self, graph):
		self.graph = graph
		self.distance = {}
		self.unvisited = {}
		self.visited = {}

	def pick_next(self, start):
		current = None
		min_distance = sys.maxsize
		for n in self.unvisited[start]:
			if min_distance > self.distance[start][n]:
				current = n
				min_distance = self.distance[start][n]
		return (min_distance, current)

	def shortest_path(self, start, end):
		if not start in self.distance:
			self.distance[start] = {}
			self.unvisited[start] = set()
			self.visited[start] = set()
			for n in self.graph:
				self.distance[start][n] = sys.maxsize
			self.unvisited[start].add(start)
			for n in self.graph[start]:
				self.unvisited[start].add(n)
		self.distance[start][start] = 0
		current = start
		while True:
			if current == end:
				break
			if current in self.unvisited[start]:
				for child in self.graph[current]:
					if not child in self.visited[start]:
						cost = self.distance[start][current] + self.graph[current][child]
						self.distance[start][child] = min(self.distance[start][child], cost)
						self.unvisited[start].add(child)
				self.visited[start].add(current)
				self.unvisited[start].discard(current)
			(min_distance, current) = self.pick_next(start)
			if min_distance == sys.maxsize:
				break
		return self.distance[start][end]
(N, M) = [int(z) for z in input().split()]
graph = {}
for n in range(1, N + 1):
	graph[n] = {}
for j in range(0, M):
	(x, y, r) = [int(z) for z in input().split()]
	graph[x][y] = r
g = Graphy(graph)
Q = int(input())
for i in range(0, Q):
	(s, e) = [int(x) for x in input().split(' ')]
	distance = g.shortest_path(s, e)
	if distance == sys.maxsize:
		print(-1)
	else:
		print(distance)


import heapq
import sys
infinity = int(1e+50)
(n, m) = tuple((int(x) for x in sys.stdin.readline().split()))
edges = tuple(({} for i in range(n)))
for i in range(m):
	(v1, v2, w) = tuple((int(x) for x in sys.stdin.readline().split()))
	v1 -= 1
	v2 -= 1
	edges[v1][v2] = w
q = int(sys.stdin.readline())
queries = []
queries_sources = set()
for i in range(q):
	(v1, v2) = tuple((int(x) for x in sys.stdin.readline().split()))
	v1 -= 1
	v2 -= 1
	queries.append((v1, v2))
	queries_sources.add(v1)

def dijkstra(s, n, edges):
	distances = [infinity] * n
	todo = []
	heapq.heappush(todo, (0, s))
	while len(todo) > 0:
		(distance, vertex) = heapq.heappop(todo)
		if distances[vertex] != infinity:
			continue
		distances[vertex] = distance
		for (next_vertex, extra_distance) in edges[vertex].items():
			next_distance = distance + extra_distance
			heapq.heappush(todo, (next_distance, next_vertex))
	return distances
distances = {}
for s in queries_sources:
	distances[s] = dijkstra(s, n, edges)
for (v1, v2) in queries:
	distance = distances[v1][v2]
	if distance == infinity:
		print(-1)
	else:
		print(distance)


INFINITY = 4294967295

class vertex:

	def __init__(self):
		self.adj = {}

def bellman_ford(V, s, sp):
	sp[s][s] = 0
	sps = sp[s]
	for i in range(0, len(V)):
		done = True
		for x in range(0, len(V)):
			for y in V[x].adj.keys():
				w = V[x].adj[y]
				if sps[y] > sps[x] + w:
					sps[y] = sps[x] + w
					done = False
		if done == True:
			break
var = input().split()
(N, M) = (int(var[0]), int(var[1]))
SP_done = [INFINITY] * N
V = []
V = [vertex() for i in range(0, N)]
SP = [[INFINITY for i in range(0, N)] for i in range(0, N)]
for i in range(0, M):
	var = input().split()
	(x, y, w) = (int(var[0]), int(var[1]), int(var[2]))
	x = x - 1
	y = y - 1
	V[x].adj[y] = w
T = int(input())
out = ''
for t in range(0, T):
	var = input().split()
	(x, y) = (int(var[0]), int(var[1]))
	x = x - 1
	y = y - 1
	if SP_done[x] != 0:
		SP_done[x] = 0
		bellman_ford(V, x, SP)
	if SP[x][y] == INFINITY:
		out += '{}\n'.format(-1)
	else:
		out += '{}\n'.format(SP[x][y])
print(out)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


INF = float('inf')

def solve(v, edges):
	sol = {u: INF for u in edges}
	sol[v] = 0
	unvisited = list(edges)
	while unvisited:
		cur = min(range(len(unvisited)), key=lambda i: sol[unvisited[i]])
		cur = unvisited.pop(cur)
		for u in edges[cur]:
			new = sol[cur] + edges[cur][u]
			if sol[u] == INF or new < sol[u]:
				sol[u] = new
	return sol
(N, M) = map(int, input().split())
edges = {v: {} for v in range(1, N + 1)}
for _ in range(M):
	(X, Y, R) = map(int, input().split())
	edges[X][Y] = R
solutions = {v: solve(v, edges) for v in edges}
Q = int(input())
for _ in range(Q):
	(A, B) = map(int, input().split())
	sol = solutions[A][B]
	print(-1 if sol == INF else sol)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(num, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, num + 1)}
for count in range(m):
	(fnum, tnum, rnum) = tuple((int(x) for x in input().strip().split()))
	try:
		numberidx = next((i for (i, (to, count)) in enumerate(edges[fnum]) if to == tnum))
		edges[fnum][numberidx] = (tnum, rnum)
	except StopIteration:
		edges[fnum].append((tnum, rnum))
questions = [tuple((int(x) for x in input().strip().split())) for count in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (frnum, tos) in questions_dict.items():
	dists = {node: -1 for node in range(1, num + 1)}
	dists[frnum] = 0
	visited = {frnum}
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[frnum, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


from heapq import heappush, heappop
from collections import defaultdict

def dijkstra(source, V):
	paths = dict()
	out_arcs = list()
	paths[source] = 0
	for out_arc in V[source]:
		heappush(out_arcs, (V[source][out_arc], out_arc))
	while len(out_arcs) > 0:
		(greedy, v) = heappop(out_arcs)
		if v in paths:
			continue
		paths[v] = greedy
		for out_arc in V[v]:
			if out_arc not in paths:
				heappush(out_arcs, (greedy + V[v][out_arc], out_arc))
	return paths
(n, m) = tuple((int(x) for x in input().split()))
(V, Q) = (defaultdict(dict), defaultdict(list))
negative_lengths = False
for _ in range(m):
	edge = tuple((int(x) for x in input().split()))
	V[edge[0]][edge[1]] = edge[2]
	if edge[2] < 0:
		negative_lengths = True
qn = int(input())
result = [-1] * qn
for i in range(qn):
	q = tuple((int(x) for x in input().split()))
	Q[q[0]].append((q[1], i))
for s in Q:
	paths = dijkstra(s, V)
	for v in Q[s]:
		if v[0] in paths:
			result[v[1]] = paths[v[0]]
for i in result:
	print(i)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


import heapq
(N, M) = input('').split()
(N, M) = (int(N), int(M))
graph = [[0 for i in range(N)] for j in range(N)]
edges = [[] for i in range(N)]
paths = [[-1 for i in range(N)] for j in range(N)]
for i in range(M):
	(x, y, r) = input('').split()
	(x, y, r) = (int(x) - 1, int(y) - 1, int(r))
	graph[x][y] = r
	edges[x].append(y)
for i in range(N):
	agenda = []
	expanded = [0 for j in range(N)]
	heapq.heappush(agenda, (0, i))
	while len(agenda) != 0:
		(r, x) = heapq.heappop(agenda)
		if expanded[x] == 1:
			continue
		expanded[x] = 1
		paths[i][x] = r
		for y in edges[x]:
			if expanded[y] == 0:
				heapq.heappush(agenda, (r + graph[x][y], y))
Q = int(input(''))
for each in range(Q):
	(x, y) = input('').split()
	(x, y) = (int(x) - 1, int(y) - 1)
	print(paths[x][y])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


graph = {}
(num_nodes, num_edges) = [int(i) for i in input().split()]
for edge in range(num_edges):
	(x, y, r) = [int(i) for i in input().split()]
	if x not in graph:
		graph[x] = {}
	graph[x][y] = r
num_questions = int(input())
question_list = []
question_sets = {}
for question in range(num_questions):
	(q, a) = [int(i) for i in input().split()]
	question_list.append((q, a))
	if q not in question_sets:
		question_sets[q] = {a}
	else:
		question_sets[q].add(a)
for q in question_sets:
	answers = question_sets[q]
	weight = {q: 0}
	steps = [q]
	while len(steps) > 0:
		step = steps.pop(0)
		if step not in graph:
			continue
		step_graph = graph[step]
		step_weight = weight[step]
		for i in step_graph:
			i_weight = step_weight + step_graph[i]
			if i not in weight or i_weight < weight[i]:
				weight[i] = i_weight
				steps.append(i)
	for a in question_sets[q]:
		if q not in graph:
			graph[q] = {}
		if a in weight:
			graph[q][a] = weight[a]
for (q, a) in question_list:
	if q == a:
		print(0)
	else:
		print(graph.get(q, {}).get(a, -1))


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


INF = 9999999999999999

def dijkstra_queries(g, queries):
	res = []
	qtable = dict()
	for (start, end) in queries:
		if (start, end) in qtable:
			res.append(res[qtable[start, end]])
			continue
		pLen = {start: 0}
		visited = [False for x in range(g[0][0] + 1)]
		cameFrom = [-1 for x in range(g[0][0] + 1)]
		pLen[start] = 0
		vlist = g[1]
		parentInPath = -1
		cameFrom[start] = -1
		for x in range(g[0][0]):
			minIndex = 0
			minWtVtex = INF
			for (i, l) in pLen.items():
				if not visited[i]:
					if l < minWtVtex:
						minWtVtex = l
						minIndex = i
			if minIndex == 0:
				break
			visited[minIndex] = True
			if minIndex == end:
				break
			for (child, wt) in vlist[minIndex]:
				try:
					if pLen[child] >= pLen[minIndex] + wt:
						pLen[child] = pLen[minIndex] + wt
						cameFrom[child] = minIndex
				except KeyError:
					pLen[child] = pLen[minIndex] + wt
					cameFrom[child] = minIndex
		tmp = minIndex
		totWt = 0
		while cameFrom[tmp] != -1:
			cache = cameFrom[tmp]
			for (adj, wt) in vlist[cache]:
				if adj == tmp:
					totWt += wt
					break
			tmp = cameFrom[tmp]
		if tmp != start:
			res.append(-1)
			qtable[start, end] = len(res) - 1
		else:
			res.append(totWt)
			qtable[start, end] = len(res) - 1
	return res

def main():
	t = 1
	for x in range(t):
		li = []
		(v, e) = map(int, input().strip().split())
		li.append([v, e])
		li.append([])
		for j in range(v + 1):
			li[1].append([])
		vlist = li[1]
		for j in range(e):
			tmp_li = list(map(lambda x: int(x), input().strip().split()))
			alreadyThere = False
			try:
				for (i, x) in enumerate(vlist[tmp_li[0]]):
					if x[0] == tmp_li[1]:
						vlist[tmp_li[0]][i][1] = tmp_li[2]
						alreadyThere = True
						break
				if not alreadyThere:
					vlist[tmp_li[0]].append([tmp_li[1], tmp_li[2]])
			except IndexError:
				vlist[tmp_li[0]].append([tmp_li[1], tmp_li[2]])
		qn = int(input())
		queries = []
		for n in range(qn):
			queries.append(list(map(lambda x: int(x), input().strip().split())))
		res = dijkstra_queries(li, queries)
		print('\n'.join((str(x) for x in res)))
main()


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


import sys
from heapq import heappush, heappop
(N, M) = input().strip().split(' ')
(N, M) = [int(N), int(M)]
costs = [{} for i in range(N + 1)]
shortestpaths = [{i: -1 for i in range(1, N + 1)} for j in range(N + 1)]
paths = []
for i in range(M):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	costs[x][y] = r
for i in range(1, N + 1):
	heappush(paths, (0, i, i))
while len(paths) > 0:
	(cost, pb, pe) = heappop(paths)
	if shortestpaths[pb][pe] == -1:
		shortestpaths[pb][pe] = cost
		for k in costs[pe].keys():
			if shortestpaths[pb][k] == -1:
				heappush(paths, (cost + costs[pe][k], pb, k))
Q = int(input().strip())
for i in range(Q):
	(a, b) = input().strip().split(' ')
	(a, b) = [int(a), int(b)]
	print(shortestpaths[a][b])


def shortestPath(source, destination, graph):
	maxHeap = dict()
	nodeDistance = dict()
	countOfNodes = len(graph)
	for eachNode in range(1, countOfNodes + 1):
		maxHeap.update({eachNode: float('inf')})
	currentNode = source
	nodeDistance.update({currentNode: 0})
	del maxHeap[currentNode]
	while maxHeap and currentNode != destination:
		if len(graph[currentNode]) == 0:
			break
		for eachEdge in graph[currentNode]:
			weightOfEdge = graph[currentNode][eachEdge]
			if eachEdge not in maxHeap:
				continue
			if maxHeap[eachEdge] > weightOfEdge + nodeDistance[currentNode]:
				maxHeap.update({eachEdge: weightOfEdge + nodeDistance[currentNode]})
		currentNode = min(maxHeap, key=maxHeap.get)
		nodeDistance.update({currentNode: maxHeap[currentNode]})
		del maxHeap[currentNode]
		if currentNode == source:
			break
		if currentNode == destination:
			break
	if destination in maxHeap:
		if maxHeap[destination] != float('inf'):
			shortPath = maxHeap[destination]
		else:
			shortPath = -1
	else:
		shortPath = nodeDistance[destination]
	return shortPath
(numberOfNodes, numberOfEdges) = map(int, input().strip().split())
directedGraph = dict()
for eachNode in range(1, numberOfNodes + 1):
	directedGraph.update({eachNode: dict()})
for edge in range(numberOfEdges):
	(startNode, endNode, weightOfEdge) = map(int, input().strip().split())
	directedGraph[startNode].update({endNode: weightOfEdge})
queries = int(input())
recentQuery = dict()
for query in range(queries):
	(source, dest) = map(int, input().strip().split())
	if (source, dest) in recentQuery:
		shortDistance = recentQuery[source, dest]
	elif source == dest:
		shortDistance = 0
	else:
		shortDistance = shortestPath(source, dest, directedGraph)
		recentQuery.update({(source, dest): shortDistance})
	print(shortDistance)


import queue

def shortest_path(graph, start, goal):
	MAX = 1000000
	dist = [MAX] * (len(graph) + 1)
	dist[start] = 0
	frontier = queue.PriorityQueue()
	frontier.put((0, start))
	while not frontier.empty():
		(weight, node) = frontier.get()
		for (n, w) in graph[node].items():
			if dist[n] > dist[node] + w:
				dist[n] = dist[node] + w
				frontier.put((dist[n], n))
	if dist[goal] == MAX:
		return -1
	return dist[goal]
(N, M) = list(map(int, input().split()))
edges = {i: {} for i in range(1, N + 1)}
memo_path_sizes = {}
for _ in range(M):
	(X, Y, R) = list(map(int, input().split()))
	edges[X][Y] = R
for _ in range(int(input())):
	(S, E) = list(map(int, input().split()))
	if (S, E) in memo_path_sizes:
		print(memo_path_sizes[S, E])
		continue
	memo_path_sizes[S, E] = shortest_path(edges, S, E)
	print(memo_path_sizes[S, E])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


import heapq as pq
(no_nodes, no_edges) = map(int, input().strip().split(' '))
queries = None
index_relations = {}
adjacent = [[] for _ in range(no_nodes)]
edges = {}
source_distances = {}

def relax(vertex):
	for edge in adjacent[vertex]:
		head = vertex
		tail = edge[1]
		weight = edge[0]
		if distance_to[tail] > distance_to[head] + weight:
			new_weight = distance_to[head] + weight
			distance_to[tail] = new_weight
			if edge in heap:
				heap_index = heap.index(edge)
				heap[heap_index] = [new_weight, tail]
				pq.heapify(heap)
			else:
				pq.heappush(heap, [new_weight, tail])
for i in range(no_nodes):
	index_relations[i + 1] = i
for _ in range(no_edges):
	(input_head, input_tail, weight) = map(int, input().strip().split(' '))
	head = index_relations[input_head]
	tail = index_relations[input_tail]
	edge = (head, tail)
	if head == tail:
		continue
	edges[edge] = weight
for edge in edges:
	head = edge[0]
	tail = edge[1]
	weight = edges[edge]
	adjacent[head].append([weight, tail])
queries = int(input().strip())
for i in range(queries):
	(input_source, input_target) = map(int, input().strip().split(' '))
	source = index_relations[input_source]
	target = index_relations[input_target]
	distance_to = None
	if source in source_distances:
		distance_to = source_distances[source]
	else:
		distance_to = [float('inf') for _ in range(no_nodes)]
		heap = []
		distance_to[source] = 0
		pq.heappush(heap, [0, source])
		while len(heap) > 0:
			min_edge = pq.heappop(heap)
			relax(min_edge[1])
		source_distances[source] = distance_to
	if distance_to[target] < float('inf'):
		print(distance_to[target])
	else:
		print(-1)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(N, M) = map(int, input().strip().split(' '))
import heapq

def floyd(start, end):
	weights = [float('inf')] * (N + 1)
	weights[start] = 0
	visited = set()
	heap = []
	heapq.heappush(heap, (weights[int(start)], start))
	p = start
	while heap:
		(w, p) = heapq.heappop(heap)
		if p not in visited and p in adj:
			visited.add(p)
			adjacent = adj[p]
			for edge2 in adjacent:
				if edge2 not in visited and dist[p, edge2] + w <= weights[edge2]:
					weights[edge2] = w + dist[p, edge2]
					heapq.heappush(heap, (weights[edge2], edge2))
	return [-1 if i == float('inf') else i for i in weights]
adj = dict()
dist = dict()
for j in range(M):
	(x, y, r) = map(int, input().strip().split(' '))
	adj.setdefault(x, set()).add(y)
	dist.setdefault((x, y), float('inf'))
	dist[x, y] = r
q = int(input().strip())
questions = []
cache = [[] for _ in range(q + 1)]
for i in range(q):
	(start, end) = map(int, input().strip().split(' '))
	questions.append(((start, end), float('inf')))
for i in range(q):
	((start, end), _) = questions[i]
	if len(cache[start]) == 0:
		cache[start] = floyd(start, end)
		ans = cache[start][end]
		questions[i] = ((start, end), ans)
	else:
		ans = cache[start][end]
	print(ans)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


import sys
from collections import defaultdict

def johnson(G):
	G.add_node(-1)
	for v in G.nodes:
		G.add_edge(-1, v, 0)
	result = bellman_ford(G, -1)
	if result is None:
		print('Negative cycle detected')
		return
	for edge in G.edges:
		from_node = edge
		for to_node in G.edges:
			if from_node != to_node and (from_node, to_node) in G.distances:
				G.distances[from_node, to_node] = G.distances[from_node, to_node] + result[to_node] - result[from_node]
	G.nodes.remove(-1)
	del G.edges[-1]
	paths = {}
	for u in G.nodes:
		visited = dijsktra(G, u)[0]
		for v in visited:
			paths[u, v] = visited[v]
	return (paths, result)

def get_real_shortest_path(paths, result, u, v):
	if (u, v) in paths:
		return paths[u, v] - result[u] + result[v]
	else:
		return float('inf')

def bellman_ford(g, source):
	paths = defaultdict(lambda : float('inf'))
	paths[source] = 0
	for i in range(len(g.nodes) - 1):
		for u in g.nodes:
			for v in g.edges[u]:
				paths[v] = min(paths[v], paths[u] + g.distances[u, v])
	for u in g.nodes:
		for v in G.edges[u]:
			if paths[v] > paths[u] + g.distances[v, u]:
				return None
	return paths

def dijsktra(graph, initial):
	visited = {initial: 0}
	path = {}
	nodes = set(graph.nodes)
	while nodes:
		min_node = None
		for node in nodes:
			if node in visited:
				if min_node is None:
					min_node = node
				elif visited[node] < visited[min_node]:
					min_node = node
		if min_node is None:
			break
		nodes.remove(min_node)
		current_weight = visited[min_node]
		for edge in graph.edges[min_node]:
			weight = current_weight + graph.distances[min_node, edge]
			if edge not in visited or weight < visited[edge]:
				visited[edge] = weight
				path[edge] = min_node
	return (visited, path)

class Graph:

	def __init__(self):
		self.nodes = set()
		self.edges = defaultdict(list)
		self.distances = defaultdict(lambda : float('inf'))

	def add_node(self, value):
		self.nodes.add(value)

	def add_edge(self, from_node, to_node, distance):
		self.edges[from_node].append(to_node)
		self.distances[from_node, to_node] = distance
G = Graph()
line1 = input().strip().split(' ')
t = int(line1[1])
n = int(line1[0])
for a0 in range(t):
	line = input().strip().split(' ')
	m = int(line[0])
	n = int(line[1])
	a = int(line[2])
	G.add_node(m)
	G.add_node(n)
	G.add_edge(m, n, a)
q = int(input().strip())
(paths, result) = johnson(G)
for i in range(q):
	line = input().strip().split(' ')
	m = int(line[0])
	n = int(line[1])
	dist_q = get_real_shortest_path(paths, result, m, n)
	if dist_q == float('inf'):
		print(-1)
	else:
		print(dist_q)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


INFINITY = 4294967295

class vertex:

	def __init__(self):
		self.adj = {}

def floyd_warshall(V, s, sp):
	sp[s][s] = 0
	sps = sp[s]
	for i in range(0, len(V)):
		done = True
		for x in range(0, len(V)):
			for y in V[x].adj.keys():
				w = V[x].adj[y]
				if sps[y] > sps[x] + w:
					sps[y] = sps[x] + w
					done = False
		if done == True:
			break
var = input().split()
(N, M) = (int(var[0]), int(var[1]))
SP_done = [INFINITY] * N
V = []
V = [vertex() for i in range(0, N)]
SP = [[INFINITY for i in range(0, N)] for i in range(0, N)]
for i in range(M):
	var = input().split()
	(x, y, w) = (int(var[0]), int(var[1]), int(var[2]))
	x = x - 1
	y = y - 1
	V[x].adj[y] = w
T = int(input())
out = ''
for t in range(0, T):
	var = input().split()
	(x, y) = (int(var[0]), int(var[1]))
	x = x - 1
	y = y - 1
	if SP_done[x] != 0:
		SP_done[x] = 0
		floyd_warshall(V, x, SP)
	if SP[x][y] == INFINITY:
		out += '{}\n'.format(-1)
	else:
		out += '{}\n'.format(SP[x][y])
print(out)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


import queue

def shortest_reach(graph, start, end=None):
	dist = {}
	visited = set()
	q = queue.PriorityQueue()
	q.put((0, start))
	dist[start] = 0
	while not q.empty():
		(u_cost, u) = q.get()
		if u == end:
			break
		if u not in visited:
			visited.add(u)
			if u in graph:
				for (v, uv_cost) in graph[u].items():
					cur_dist = u_cost + uv_cost
					if v not in dist or cur_dist < dist[v]:
						dist[v] = cur_dist
						q.put((cur_dist, v))
	return dist
(N, M) = list(map(int, input().strip().split()))
graph = {}
for i in range(M):
	[u, v, cost] = list(map(int, input().split()))
	u_edges = graph.get(u, {})
	u_edges[v] = cost
	graph[u] = u_edges
Q = int(input())
queries = {}
q_list = []
for q in range(Q):
	(a, b) = list(map(int, input().split()))
	queries[a] = queries.get(a, []) + [b]
	q_list.append((a, b))
res = {}
for (a, targets) in queries.items():
	dist = shortest_reach(graph, a)
	for b in targets:
		if b in dist:
			res[a, b] = dist[b]
		else:
			res[a, b] = -1
for q in q_list:
	print(res[q])


import heapq
(n, m) = map(int, input().split())
adj = [dict() for _ in range(n + 1)]
for _ in range(m):
	(u, v, d) = map(int, input().split())
	adj[u][v] = d
dist = [[-2 for _ in range(n + 1)] for _ in range(n + 1)]
temp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n + 1):
	dist[i][i] = 0
	temp[i][i] = 0
candidates = [[] for _ in range(n + 1)]
q = int(input())
for _ in range(q):
	(source, dest) = map(int, input().split())
	udist = dist[source]
	utemp = temp[source]
	if udist[dest] == -2:
		edges = candidates[source]
		if len(edges) == 0:
			cur = source
		else:
			while True:
				(d, v) = heapq.heappop(edges)
				if udist[v] == -2:
					utemp[v] = d
					udist[v] = d
					cur = v
					break
		while True:
			for v in adj[cur]:
				newd = udist[cur] + adj[cur][v]
				if utemp[v] == -1 or newd < utemp[v]:
					utemp[v] = newd
					heapq.heappush(edges, (newd, v))
			if cur == dest or len(edges) == 0:
				break
			while True:
				(d, v) = heapq.heappop(edges)
				if udist[v] == -2:
					utemp[v] = d
					udist[v] = d
					cur = v
					break
	if udist[dest] == -2:
		udist[dest] = -1
	print(udist[dest])


import sys
sys.setrecursionlimit(2048)
from functools import total_ordering

class IndexMinPQ:

	def __init__(self, size):
		self.pq = {i: -1 for i in range(1, size + 1)}
		self.qp = {i: -1 for i in range(size + 1)}
		self.keys = {}
		self.N = 0

	def exch(self, i, j):
		(self.pq[i], self.pq[j]) = (self.pq[j], self.pq[i])
		self.qp[self.pq[i]] = i
		self.qp[self.pq[j]] = j

	def gt(self, i, j):
		return self.keys[self.pq[i]] > self.keys[self.pq[j]]

	def swim(self, k):
		while k > 1 and self.gt(int(k / 2), k):
			self.exch(k, int(k / 2))
			k = int(k / 2)

	def sink(self, k):
		while 2 * k <= self.N:
			j = 2 * k
			if j < self.N and self.gt(j, j + 1):
				j += 1
			if not self.gt(k, j):
				break
			self.exch(k, j)
			k = j

	def insert(self, i, key):
		assert not self.contains(i)
		self.N += 1
		self.qp[i] = self.N
		self.keys[i] = key
		self.pq[self.N] = i
		self.swim(self.N)

	def min(self):
		return self.pq[1]

	def delete_min(self):
		min = self.pq[1]
		self.exch(1, self.N)
		self.N -= 1
		self.sink(1)
		assert min == self.pq[self.N + 1]
		self.qp[min] = -1
		del self.keys[min]
		self.pq[self.N + 1] = -1
		return min

	def decrease_key(self, i, key):
		assert self.contains(i)
		self.keys[i] = key
		self.swim(self.qp[i])

	def contains(self, k):
		return self.qp[k] > -1

@total_ordering
class WeightedDiedge:

	def __init__(self, v, w, weight):
		(self.v, self.w) = (v, w)
		self.weight = weight

	def out(self):
		return self.v

	def to(self):
		return self.w

	def __lt__(self, other):
		return self.weight < other.weight

	def __eq__(self, other):
		return self.weight == self.weight

	def __str__(self):
		return '{} -- {} --> {}'.format(self.out(), self.weight, self.to())

class WeightedDigraph:

	def __init__(self, V):
		(self.V, self.E) = (V, 0)
		self._adj = {i: [] for i in range(1, self.V + 1)}

	def add_edge(self, v, w, weight):
		self._adj[v] = list((e for e in self._adj[v] if e.to() != w))
		self._adj[v].append(WeightedDiedge(v, w, weight))
		self.E += 1

	def adj(self, v):
		return self._adj[v]

class DijkstraSP:

	def __init__(self, s, G):
		self.dist_to = {i: float('inf') for i in G._adj}
		self.edge_to = {i: None for i in G._adj}
		self.pq = IndexMinPQ(G.V + 1)
		self.dist_to[s] = 0
		self.pq.insert(s, self.dist_to[s])
		while self.pq.N > 0:
			self.relax(self.pq.delete_min(), G)

	def relax(self, v, G):
		for e in G.adj(v):
			w = e.to()
			if self.dist_to[v] + e.weight < self.dist_to[w]:
				self.dist_to[w] = self.dist_to[v] + e.weight
				self.edge_to[w] = e
				if self.pq.contains(w):
					self.pq.decrease_key(w, self.dist_to[w])
				else:
					self.pq.insert(w, self.dist_to[w])

	def has_path_to(self, v):
		assert v in self.dist_to
		return self.dist_to[v] < float('inf')

	def path_to(self, v):
		if self.edge_to[v] is None:
			return
		edge = self.edge_to[v]
		yield from self.path_to(edge.out())
		yield edge

class DijkstraAllPairsSP:

	def __init__(self, G):
		self.all = {}
		for v in G._adj:
			self.all[v] = DijkstraSP(v, G)

	def path(self, s, t):
		yield from self.all[s].path_to(v)

	def dist(self, s, t):
		return self.all[s].dist_to[t]
(N, M) = tuple(map(int, input().split()))
G = WeightedDigraph(N)
for e_ind in range(M):
	(v, w, weight) = [f(arg) for (f, arg) in zip((int, int, int), input().split())]
	G.add_edge(v, w, weight)
dasp = DijkstraAllPairsSP(G)
T = int(input())
for t in range(T):
	(s, t) = tuple(map(int, input().split()))
	dist = dasp.dist(s, t)
	if dist < float('inf'):
		print(dist)
	else:
		print(-1)


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])


class Graph:

	def __init__(self, N):
		self.nodes = [[] for n in range(N + 1)]
		pass

	def size(self):
		return len(self.nodes)

	def add_edge(self, a, b, dist):
		neighbors = self.nodes[a]
		for i in range(len(neighbors)):
			(n, d) = neighbors[i]
			if n == b:
				neighbors[i] = (b, dist)
				return
		neighbors.append((b, dist))

	def get_neighbors(self, a):
		return self.nodes[a]
INFINITE = 350 * 400

def get_min(values, valid_keys):
	min_key = 0
	min_value = INFINITE
	for key in valid_keys:
		if values[key] < min_value:
			min_value = values[key]
			min_key = key
	return (min_key, min_value)

def dijkstra(graph, a, b):
	dist_map = [INFINITE] * graph.size()
	dist_map[a] = 0
	Q = set()
	Q.add(a)
	while Q:
		(u, dist) = get_min(dist_map, Q)
		Q.remove(u)
		if u == b:
			return dist
		neighbors = graph.get_neighbors(u)
		for (v, d) in neighbors:
			alt = dist + d
			old = dist_map[v]
			if alt < old:
				dist_map[v] = alt
				Q.add(v)
	return -1
(N, M) = map(int, input().split())
graph = Graph(N)
for m in range(M):
	(a, b, dist) = map(int, input().split())
	graph.add_edge(a, b, dist)
Q = int(input())
cache = {}
for q in range(Q):
	(a, b) = map(int, input().split())
	if (a, b) in cache:
		print(cache[a, b])
		continue
	dist = dijkstra(graph, a, b)
	cache[a, b] = dist
	print(dist)


from collections import defaultdict

def dijkstra(g, s):
	dist = [10 ** 6 for _ in range(n)]
	dist[s] = 0
	marked = [0 for _ in range(n)]
	v = s
	marked[v] = 1
	while True:
		for (node, wt) in g[v]:
			dist[node] = min(dist[node], dist[v] + wt)
		min_val = 10 ** 6
		marked_node = -1
		for i in range(n):
			if marked[i] == 0 and dist[i] < min_val:
				min_val = dist[i]
				marked_node = i
		if marked_node != -1:
			v = marked_node
			marked[v] = 1
		else:
			break
	dist_from[s] = [0 for _ in range(n)]
	for i in range(n):
		if dist[i] != 10 ** 6:
			dist_from[s][i] = dist[i]
		else:
			dist_from[s][i] = -1
(n, m) = map(int, input().split())
ip = [[-1 for _ in range(n)] for _ in range(n)]
for _ in range(m):
	(x, y, r) = map(int, input().split())
	x -= 1
	y -= 1
	ip[x][y] = r
g = [[] for _ in range(n)]
for i in range(n):
	for j in range(n):
		if ip[i][j] != -1:
			g[i].append((j, ip[i][j]))
dist_from = defaultdict(list)
q = int(input())
for _ in range(q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if len(dist_from[a]) == 0:
		dijkstra(g, a)
	print(dist_from[a][b])


import sys
from collections import defaultdict
from collections import namedtuple
HeapElement = namedtuple('HeapElement', ['heap_key', 'key', 'data'])

class UpdatableHeap(object):
	ZERO_POZ = 0

	def __init__(self):
		self.heap = []
		self.register = {}

	def __len__(self):
		return len(self.heap)

	def push(self, heap_key, key, data):
		el = HeapElement(heap_key, key, data)
		self.heap.append(el)
		idx = self.register[key] = len(self.heap) - 1
		self.bubble_up(idx)

	def pop(self):
		self.swap_heap_and_register(self.ZERO_POZ, len(self.heap) - 1)
		del self.register[self.heap[-1].key]
		result_el = self.heap.pop()
		self.bubble_down(self.ZERO_POZ)
		return result_el

	def decrease(self, new_heap_key, key, data):
		idx = self.register.get(key)
		if not idx:
			pos = self.push(new_heap_key, key, data)
		else:
			self.heap[idx] = HeapElement(new_heap_key, key, data)
			pos = self.bubble_up(idx)
		return pos

	def update(self, new_heap_key, key, data):
		idx = self.register[key]
		self.heap[idx] = HeapElement(new_heap_key, key, data)
		self.bubble_up(idx)
		self.bubble_down(idx)

	def sorted_iterator(self):
		heap_store = self.heap[:]
		while self.heap:
			yield self.pop()
		self.heap[:] = heap_store

	def heapsort(self, lst):
		(result, heap_store) = ([], [])
		for x in lst:
			self.push(*x)
		heap_store = self.heap[:]
		while self.heap:
			x = self.pop()
			result.append((x.heap_key, x.key, x.data))
		self.heap = heap_store[:]
		return result

	def bubble_up(self, pos):
		while pos > self.ZERO_POZ:
			parent_idx = pos - 1 >> 1
			pos_key = self.heap[pos].key
			if self.heap[parent_idx] <= self.heap[pos]:
				self.register[pos_key] = pos
				return pos
			self.swap_heap_and_register(pos, parent_idx)
			pos = parent_idx
		return pos

	def bubble_down(self, pos):
		while (pos << 1) + 1 < len(self.heap):
			(chld_idx, chld2_idx) = ((pos << 1) + 1, (pos << 1) + 2)
			min_chld_idx = chld2_idx if chld2_idx < len(self.heap) and self.heap[chld2_idx] < self.heap[chld_idx] else chld_idx
			if self.heap[pos] <= self.heap[min_chld_idx]:
				return pos
			self.swap_heap_and_register(pos, min_chld_idx)
			pos = min_chld_idx
		return pos

	def swap_heap_and_register(self, idx, idx2):
		(idx_key, idx2_key) = (self.heap[idx].key, self.heap[idx2].key)
		(self.register[idx2_key], self.register[idx_key]) = (idx, idx2)
		(self.heap[idx2], self.heap[idx]) = (self.heap[idx], self.heap[idx2])

class Graph(object):

	def __init__(self, adj_list, lst_of_vertices):
		self.v = lst_of_vertices
		self.adj_list = adj_list

class DijkstraSearch(object):

	def __init__(self, g):
		self.g = g
		self.queue = UpdatableHeap()
		self.prev = set()
		self.vds = {}

	def init_q(self, s):
		for v in self.g.v:
			if v != s:
				vd = HeapElement(heap_key=float('inf'), key=v, data=None)
				self.queue.push(*vd)
			else:
				vd = HeapElement(heap_key=0, key=s, data=None)
				self.queue.push(*vd)
			self.vds[vd.key] = vd

	def find_shortest_paths(self, s):
		vd = HeapElement(heap_key=0, key=s, data=None)
		self.queue.push(*vd)
		self.vds[vd.key] = vd
		while len(self.queue):
			current = self.queue.pop()
			self.prev.add(current.key)
			for (u, weight) in self.g.adj_list[current.key].items():
				if u not in self.prev:
					if not self.vds.get(u) or (self.vds.get(u) and current.heap_key + weight < self.vds[u].heap_key):
						new_heap_key = current.heap_key + weight
						self.vds[u] = HeapElement(heap_key=new_heap_key, key=u, data=None)
						self.queue.decrease(*self.vds[u])
		sorted_vertices = sorted(self.vds.keys())
		sorted_weights = [self.vds[v].heap_key if v in sorted_vertices else '-1' for v in self.g.v if v != s]
		return self.vds

	def str_of_sorted_shortest_paths(self, s):
		sws = self.find_shortest_paths(s)
		return ' '.join([str(w) if w != float('inf') else '-1' for w in sws])

def enter_data():
	adj_lst = defaultdict(dict)
	queries = defaultdict(set)
	lines = sys.stdin.readlines()
	[n, m] = [int(x.strip(), 10) for x in lines[0].split()]
	vertices = list(range(1, n + 1))
	for j in range(1, m + 1):
		[x, y, r] = [int(t.strip(), 10) for t in lines[j].split()]
		adj_lst[x][y] = r
	q = int(lines[m + 1].strip(), 10)
	jq = m + 2
	for j in range(q):
		[a, b] = [int(t.strip(), 10) for t in lines[jq + j].split()]
		queries[a].add((b, j))
	g = Graph(adj_lst, vertices)
	return (g, queries)

def perform_queries(g, queries):
	answers_to_be_ordered = []
	a_append = answers_to_be_ordered.append
	for x in queries:
		dijkstra = DijkstraSearch(g)
		vds = dijkstra.find_shortest_paths(x)
		for (y, order) in queries[x]:
			dist = 0 if x == y else vds[y].heap_key if vds.get(y) else -1
			a_append((order, dist))
	answers_to_be_ordered.sort()
	answers = [dist for (order, dist) in answers_to_be_ordered]
	return answers

def solution():
	(g, queries) = enter_data()
	answers = perform_queries(g, queries)
	for ans in answers:
		print(ans)
solution()


import math

def printv(v):
	if v >= 1000000000:
		print(-1)
	else:
		print(v)
(n, m) = map(int, input().split())
adj = []
cost = []
dist = [1000000000] * n
g = set()
a = []
con = set()
for i in range(n):
	adj.append([])
	cost.append([1000000000] * n)
	cost[i][i] = 0
	g.add(i)
	a.append([1000000000] * n)
for c in range(m):
	(x, y, r) = map(int, input().split())
	adj[x - 1].append(y - 1)
	cost[x - 1][y - 1] = r
q = int(input())
for _ in range(q):
	(s, f) = map(int, input().split())
	s = s - 1
	f = f - 1
	if s in con:
		printv(a[s][f])
	else:
		S = {s}
		con.add(s)
		for i in range(0, n):
			dist[i] = cost[s][i]
		for k in range(1, n):
			mi = 1000000000
			for u in g - S:
				if dist[u] <= mi:
					mi = dist[u]
					m = u
			S.add(m)
			for w in adj[m]:
				if w not in S:
					if dist[w] > dist[m] + cost[m][w]:
						dist[w] = dist[m] + cost[m][w]
		for i in range(n):
			a[s][i] = dist[i]
		printv(a[s][f])


(n, m) = tuple((int(x) for x in input().strip().split()))
edges = {node: list() for node in range(1, n + 1)}
for _ in range(m):
	(f, t, r) = tuple((int(x) for x in input().strip().split()))
	try:
		idx = next((i for (i, (to, _)) in enumerate(edges[f]) if to == t))
		edges[f][idx] = (t, r)
	except StopIteration:
		edges[f].append((t, r))
questions = [tuple((int(x) for x in input().strip().split())) for _ in range(int(input()))]
questions_dict = dict()
for (fr, to) in questions:
	if fr not in questions_dict:
		questions_dict[fr] = {to}
	else:
		questions_dict[fr].add(to)
answers = dict()
for (fr, tos) in questions_dict.items():
	visited = {fr}
	dists = {node: -1 for node in range(1, n + 1)}
	dists[fr] = 0
	while visited:
		next_visited = set()
		for node in visited:
			nd = dists[node]
			for (node2, r) in edges[node]:
				nw = nd + r
				if dists[node2] == -1 or nw < dists[node2]:
					dists[node2] = nw
					next_visited.add(node2)
		visited = next_visited
	for to in tos:
		answers[fr, to] = dists[to]
for (fr, to) in questions:
	print(answers[fr, to])