You are a mayor of Berlyatov. There are $n$ districts and $m$ two-way roads between them. The $i$-th road connects districts $x_i$ and $y_i$. The cost of travelling along this road is $w_i$. There is some path between each pair of districts, so the city is connected.

There are $k$ delivery routes in Berlyatov. The $i$-th route is going from the district $a_i$ to the district $b_i$. There is one courier on each route and the courier will always choose the cheapest (minimum by total cost) path from the district $a_i$ to the district $b_i$ to deliver products.

The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).

You can make at most one road to have cost zero (i.e. you choose at most one road and change its cost with $0$).

Let $d(x, y)$ be the cheapest cost of travel between districts $x$ and $y$.

Your task is to find the minimum total courier routes cost you can achieve, if you optimally select the some road and change its cost with $0$. In other words, you have to find the minimum possible value of $\sum\limits_{i = 1}^{k} d(a_i, b_i)$ after applying the operation described above optimally.


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($2 \le n \le 1000$; $n - 1 \le m \le min(1000, \frac{n(n-1)}{2})$; $1 \le k \le 1000$) — the number of districts, the number of roads and the number of courier routes.

The next $m$ lines describe roads. The $i$-th road is given as three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$; $1 \le w_i \le 1000$), where $x_i$ and $y_i$ are districts the $i$-th road connects and $w_i$ is its cost. It is guaranteed that there is some path between each pair of districts, so the city is connected. It is also guaranteed that there is at most one road between each pair of districts.

The next $k$ lines describe courier routes. The $i$-th route is given as two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) — the districts of the $i$-th route. The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).


-----Output-----

Print one integer — the minimum total courier routes cost you can achieve (i.e. the minimum value $\sum\limits_{i=1}^{k} d(a_i, b_i)$, where $d(x, y)$ is the cheapest cost of travel between districts $x$ and $y$) if you can make some (at most one) road cost zero.


-----Examples-----
Input
6 5 2
1 2 5
2 3 7
2 4 4
4 5 2
4 6 8
1 6
5 3

Output
22

Input
5 5 4
1 2 5
2 3 4
1 4 3
4 3 7
3 5 2
1 5
1 3
3 3
1 5

Output
13



-----Note-----

The picture corresponding to the first example:

[Image]

There, you can choose either the road $(2, 4)$ or the road $(4, 6)$. Both options lead to the total cost $22$.

The picture corresponding to the second example:

$A$

There, you can choose the road $(3, 4)$. This leads to the total cost $13$.

Source: codeforces | Difficulty: EASY


Solutions:
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from heapq import *
data = [list(map(int, line.split())) for line in sys.stdin.readlines()]
(n, m, k) = data[0]
dist = [[1000000000] * (n + 1) for _ in range(n + 1)]
adj = [[] for _ in range(n + 1)]
for (u, v, w) in data[1:m + 1]:
	adj[u].append((v, w))
	adj[v].append((u, w))
for s in range(1, n + 1):
	dist[s][s] = 0
	heap = [(0, s)]
	while heap:
		(d, u) = heappop(heap)
		if d != dist[s][u]:
			continue
		else:
			for (v, w) in adj[u]:
				nd = d + w
				if nd < dist[s][v]:
					dist[s][v] = nd
					heappush(heap, (nd, v))
ans = float('inf')
for (u, v, _) in data[1:m + 1]:
	now = 0
	for (a, b) in data[m + 1:]:
		now += min(dist[a][b], dist[a][u] + dist[v][b], dist[a][v] + dist[u][b])
	ans = min(ans, now)
print(ans)


import heapq
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def dijkstra(source, neigh, dic):
	n = len(neigh)
	distance = [float('inf')] * n
	distance[source] = 0
	visited = [False] * n
	heap = []
	heapq.heappush(heap, (0, source))
	while heap:
		temp = heapq.heappop(heap)
		(d, index) = (temp[0], temp[1])
		if visited[index]:
			continue
		visited[index] = True
		for ele in neigh[index]:
			if visited[ele]:
				continue
			newdistance = distance[index] + dic[ele, index]
			if newdistance > distance[ele]:
				continue
			heapq.heappush(heap, (newdistance, ele))
			distance[ele] = newdistance
	return distance
(n, m, k) = map(int, input().split())
neigh = [[] for i in range(n)]
start = [0] * k
end = [0] * k
dic = {}
for i in range(m):
	path = list(map(int, input().split()))
	neigh[path[0] - 1].append(path[1] - 1)
	neigh[path[1] - 1].append(path[0] - 1)
	dic[path[0] - 1, path[1] - 1] = path[2]
	dic[path[1] - 1, path[0] - 1] = path[2]
for i in range(k):
	(temp1, temp2) = map(int, input().split())
	start[i] = temp1 - 1
	end[i] = temp2 - 1
matrix = []
for i in range(n):
	matrix.append(dijkstra(i, neigh, dic))
ans = 2147483647
for ele in dic:
	tot = 0
	for i in range(k):
		tot += min(matrix[start[i]][end[i]], matrix[start[i]][ele[0]] + matrix[ele[1]][end[i]], matrix[start[i]][ele[1]] + matrix[ele[0]][end[i]])
	ans = min(ans, tot)
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from heapq import heappop, heappush

def dijkstra(graph, alpha):
	n = len(graph)
	distance = [float('inf')] * n
	distance[alpha] = 0
	queue = []
	heappush(queue, (0, alpha))
	while queue:
		(length, v) = heappop(queue)
		for (x, dist) in graph[v]:
			if dist + length < distance[x]:
				distance[x] = dist + length
				heappush(queue, (dist + length, x))
	return distance
for _ in range(int(input()) if not True else 1):
	(n, m, q) = map(int, input().split())
	graph = [[] for __ in range(n + 1)]
	contrib = {}
	for i in range(m):
		(x, y, k) = map(int, input().split())
		contrib[min(x, y), max(x, y)] = 0
		graph[x] += [(y, k)]
		graph[y] += [(x, k)]
	dist = [[]]
	for i in range(1, n + 1):
		dist += [dijkstra(graph, i)]
	ans = 0
	for i in range(q):
		(a, b) = map(int, input().split())
		if a == b:
			continue
		for (x, y) in contrib:
			contrib[x, y] += max(0, dist[a][b] - dist[a][x] - dist[b][y], dist[a][b] - dist[b][x] - dist[a][y])
		ans += dist[a][b]
	subtract = max((contrib[k] for k in contrib))
	print(ans - subtract)


import sys, heapq
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
EDGE = [tuple(map(int, input().split())) for i in range(m)]
E = [[] for i in range(n + 1)]
for (x, y, w) in EDGE:
	E[x].append((y, w))
	E[y].append((x, w))
ANS = 0
COST = [[1 << 30] * (n + 1) for i in range(n + 1)]
QL = [tuple(map(int, input().split())) for i in range(k)]
for x in range(1, n + 1):
	COST[x][x] = 0
	Q = [(0, x)]
	while Q:
		(cost, fr) = heapq.heappop(Q)
		if cost > COST[x][fr]:
			continue
		for (to, c) in E[fr]:
			if COST[x][to] > cost + c:
				COST[x][to] = cost + c
				heapq.heappush(Q, (COST[x][to], to))
ANS = 1 << 60
for (x, y, _) in EDGE:
	A = 0
	for (fr, to) in QL:
		A += min(COST[fr][to], COST[fr][x] + COST[to][y], COST[to][x] + COST[fr][y])
	ANS = min(ANS, A)
print(ANS)


(n, m, k) = map(int, input().split())
g = [[] for _ in range(n)]
E = []
for i in range(m):
	(x, y, w) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	g[x].append((w, y))
	g[y].append((w, x))
	E.append((x, y))
AB = []
for i in range(k):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	AB.append((a, b))
import heapq
INF = 10 ** 18

def dijkstra_heap(s, edge):
	n = len(edge)
	d = [INF] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, (e[0] + d[v], e[1]))
	return d
D = []
for i in range(n):
	d = dijkstra_heap(i, g)
	D.append(d)
ans = 10 ** 18
for (x, y) in E:
	temp = 0
	for (a, b) in AB:
		temp += min(D[a][b], D[a][x] + D[y][b], D[a][y] + D[x][b])
	ans = min(temp, ans)
print(ans)


import sys
from heapq import heappush, heappop, heapify

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)
inf = float('inf')
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
from heapq import heappush, heappop, heapify

def dijkstra(edge, st):
	n = len(edge)
	d = [0 if st == i else inf for i in range(n)]
	q = [(0, st)]
	heapify(q)
	v = [False] * n
	while q:
		(dist, cur) = heappop(q)
		if v[cur]:
			continue
		v[cur] = True
		for (dst, dist) in edge[cur]:
			alt = d[cur] + dist
			if alt < d[dst]:
				d[dst] = alt
				heappush(q, (alt, dst))
	return d
ans = 0
(n, m, k) = LI()
(g, oin) = GI(n, m)
r = []
for i in range(k):
	r += (LI_(),)
dist = []
for i in range(n):
	d = dijkstra(g, i)
	dist += (d,)
ans = inf
for i in range(m):
	(x, y, w) = oin[i]
	x -= 1
	y -= 1
	alt = 0
	for j in range(k):
		(a, b) = r[j]
		tmp = dist[a][x] + dist[y][b]
		if tmp > dist[a][y] + dist[x][b]:
			tmp = dist[a][y] + dist[x][b]
		if tmp > dist[a][b]:
			tmp = dist[a][b]
		alt += tmp
	if ans > alt:
		ans = alt
print(ans)


def read_generator():
	while True:
		tokens = input().split(' ')
		for t in tokens:
			yield t
reader = read_generator()

def readword():
	return next(reader)

def readint():
	return int(next(reader))

def readfloat():
	return float(next(reader))

def readline():
	return input()

def solve(n):
	return n
import heapq

def finddist(s, g, n):
	d = [10 ** 10] * n
	handled = [False] * n
	d[s] = 0
	heap = [(0, s)]
	heapq.heapify(heap)
	while len(heap) > 0:
		(l, v) = heapq.heappop(heap)
		if not handled[v]:
			handled[v] = True
			for (nextV, w) in g[v]:
				if d[nextV] > d[v] + w:
					d[nextV] = d[v] + w
					heapq.heappush(heap, (d[nextV], nextV))
	return d
tests = 1
for t in range(tests):
	n = readint()
	m = readint()
	k = readint()
	g = [[] for _ in range(n)]
	e = []
	for _ in range(m):
		(v1, v2, w) = (readint() - 1, readint() - 1, readint())
		g[v1].append((v2, w))
		g[v2].append((v1, w))
		e.append((v1, v2))
	p = [(readint() - 1, readint() - 1) for _ in range(k)]
	d = [finddist(i, g, n) for i in range(n)]
	res = 0
	for (s1, s2) in p:
		res += d[s1][s2]
	for (v1, v2) in e:
		s = 0
		for (s1, s2) in p:
			s += min(d[s1][s2], d[s1][v1] + d[v2][s2], d[s1][v2] + d[v1][s2])
		res = min(res, s)
	print(res)


(n, m, k) = map(int, input().split())
inf = 1000001
g = [[] for _ in range(n)]
e = []
for i in range(m):
	(a, b, w) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append((b, w))
	g[b].append((a, w))
	e.append((a, b))

def f(s, g):
	d = [inf] * n
	d[s] = 0
	q = [s]
	i = 0
	while i < len(q):
		(w, v) = divmod(q[i], n)
		i += 1
		if d[v] != w:
			continue
		for (u, w) in g[v]:
			if d[v] + w < d[u]:
				d[u] = d[v] + w
				q.append(u + n * d[u])
	return d
p = [f(s, g) for s in range(n)]
(t, s) = (0, [0] * len(e))
for i in range(k):
	(x, y) = map(int, input().split())
	if x == y:
		continue
	x -= 1
	y -= 1
	t += p[x][y]
	for (i, (a, b)) in enumerate(e):
		d = min(p[x][a] + p[b][y], p[x][b] + p[a][y])
		if p[x][y] > d:
			s[i] += p[x][y] - d
print(t - max(s))


import sys
input = sys.stdin.readline
from heapq import *

def dijkstra(s):
	dist = [10 ** 18] * n
	dist[s] = 0
	pq = []
	heappush(pq, (0, s))
	while pq:
		(d, v) = heappop(pq)
		if dist[v] < d:
			continue
		for (nv, w) in G[v]:
			if dist[nv] > dist[v] + w:
				dist[nv] = dist[v] + w
				heappush(pq, (dist[nv], nv))
	return dist
(n, m, k) = map(int, input().split())
G = [[] for _ in range(n)]
edges = []
for _ in range(m):
	(x, y, w) = map(int, input().split())
	G[x - 1].append((y - 1, w))
	G[y - 1].append((x - 1, w))
	edges.append((x - 1, y - 1))
dists = [dijkstra(i) for i in range(n)]
ab = [tuple(map(int, input().split())) for _ in range(k)]
ans = 10 ** 18
for (x, y) in edges:
	cand = 0
	for (a, b) in ab:
		cand += min(dists[a - 1][b - 1], dists[a - 1][x] + dists[y][b - 1], dists[a - 1][y] + dists[x][b - 1])
	ans = min(ans, cand)
print(ans)


import heapq
import logging
import sys
from inspect import currentframe
input = sys.stdin.readline
logging.basicConfig(level=logging.DEBUG)

def dbg(*args):
	id2names = {id(v): k for (k, v) in currentframe().f_back.f_locals.items()}
	logging.debug(', '.join((id2names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args)))

def dijkstra(s, edges):
	d = [float('inf')] * len(edges)
	d[s] = 0
	pq = [(0, s)]
	while pq:
		(c, v) = heapq.heappop(pq)
		if d[v] < c:
			continue
		for (c2nv, nv) in edges[v]:
			if c + c2nv < d[nv]:
				d[nv] = c + c2nv
				heapq.heappush(pq, (d[nv], nv))
	return d
(n, m, k) = map(int, input().split())
es = [[] for _ in range(n)]
e_list = []
for _ in range(m):
	(x, y, w) = map(int, input().split())
	x -= 1
	y -= 1
	es[x].append((w, y))
	es[y].append((w, x))
	e_list.append((w, x, y))
paths = []
for _ in range(k):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	paths.append((a, b))
d = [dijkstra(i, es) for i in range(n)]
ans = float('inf')
for (w, x, y) in e_list:
	cost = 0
	for path in paths:
		(a, b) = path
		cost += min(d[a][b], d[a][x] + d[y][b], d[a][y] + d[x][b])
	ans = min(ans, cost)
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from heapq import heappush, heappop

def graph_undirected():
	(n, m, k) = [int(x) for x in input().split()]
	graph = {}
	edges = []
	for i in range(m):
		(vertex, neighbour, weight) = [int(x) for x in input().split()]
		edges.append((vertex, neighbour))
		if vertex in graph:
			graph[vertex].append((weight, neighbour))
		else:
			graph[vertex] = [(weight, neighbour)]
		if neighbour in graph:
			graph[neighbour].append((weight, vertex))
		else:
			graph[neighbour] = [(weight, vertex)]
	return (graph, n, k, edges)
(graph, n, k, edges) = graph_undirected()
routes = []
for i in range(k):
	(a, b) = [int(x) for x in input().split()]
	routes.append((a, b))

def dijkastra(graph, n, currnode):
	isvisited = [False for x in range(n + 1)]
	weight = [float('inf') for x in range(n + 1)]
	weight[currnode] = 0
	h = []
	heappush(h, (0, currnode))
	while h:
		currnode = heappop(h)[1]
		if isvisited[currnode] == False:
			isvisited[currnode] = True
			for neighbour in graph[currnode]:
				if isvisited[neighbour[1]] == False:
					if neighbour[0] + weight[currnode] < weight[neighbour[1]]:
						weight[neighbour[1]] = neighbour[0] + weight[currnode]
						heappush(h, (weight[neighbour[1]], neighbour[1]))
	return weight
mindis = [[]]
for i in range(1, n + 1):
	mindis.append(dijkastra(graph, n, i))
total = 0
for i in range(k):
	total += mindis[routes[i][0]][routes[i][1]]
for (a, b) in edges:
	newtotal = 0
	for (start, end) in routes:
		newtotal += min(mindis[start][end], mindis[start][a] + mindis[b][end], mindis[start][b] + mindis[a][end])
	total = min(total, newtotal)
print(total)


import os
import sys
from io import BytesIO, IOBase
from heapq import heappop, heappush

def main():
	(n, m, k) = getints()
	adj = [[] for _ in range(n)]
	dist = [[int(1000000000.0)] * n for _ in range(n)]
	edges = []
	route = []
	for _ in range(m):
		(u, v, w) = getint1()
		w += 1
		adj[u].append((v, w))
		adj[v].append((u, w))
		edges.append((u, v))
	for _ in range(k):
		(a, b) = getint1()
		route.append((a, b))
	for s in range(n):
		dist[s][s] = 0
		pq = [(0, s)]
		while pq:
			(d, u) = heappop(pq)
			if d != dist[s][u]:
				continue
			for (v, w) in adj[u]:
				nd = dist[s][u] + w
				if dist[s][v] > nd:
					dist[s][v] = nd
					heappush(pq, (nd, v))
	ans = int(1000000000.0)
	for (u, v) in edges:
		cost = 0
		for (a, b) in route:
			cost += min(dist[a][b], dist[a][u] + dist[v][b], dist[a][v] + dist[u][b])
		ans = min(ans, cost)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def getint():
	return int(input())

def getints():
	return list(map(int, input().split()))

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))
main()


import sys, math
import io, os
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = int(1000000000.0) + 7

def dijkstra(n, graph, start):
	dist = [float('inf')] * n
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					dist[w] = edge_len + path_len
					heappush(queue, (edge_len + path_len, w))
	return dist
(n, m, k) = mdata()
graph = [[] for i in range(n)]
d = dd(int)
edges = []
for i in range(m):
	(u, v, w) = mdata()
	graph[u - 1].append([v - 1, w])
	graph[v - 1].append([u - 1, w])
	edges.append([u - 1, v - 1])
couriers = [mdata() for i in range(k)]
dist = [dijkstra(n, graph, i) for i in range(n)]
ans = INF
for (u, v) in edges:
	ans1 = 0
	for (x, y) in couriers:
		ans1 += min(dist[x - 1][y - 1], dist[x - 1][u] + dist[y - 1][v], dist[x - 1][v] + dist[y - 1][u])
	ans = min(ans1, ans)
out(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)

def dijkstra(n, graph, start):
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)

def solve(case):
	(n, m, k) = sep()
	g = [[] for i in range(n)]
	edges = {}
	for i in range(m):
		(a, b, c) = sep()
		a -= 1
		b -= 1
		edges[a, b] = c
		g[a].append((b, c))
		g[b].append((a, c))
	dist = []
	tochck = []
	for i in range(k):
		(a, b) = sep()
		a -= 1
		b -= 1
		tochck.append((a, b))
	for i in range(n):
		(temp, p) = dijkstra(n, g, i)
		dist.append(temp)
	ans = inf
	for i in edges:
		curr = 0
		(x, y) = i
		for (a, b) in tochck:
			curr += min(dist[a][b], dist[a][x] + dist[y][b], dist[a][y] + dist[x][b])
		ans = min(ans, curr)
	print(ans)
testcase(1)


import heapq
(n, m, k) = map(int, input().split())
E = [[] for _ in range(n)]
edges = []
for _ in range(m):
	(u, v, w) = map(int, input().split())
	E[u - 1].append((v - 1, w))
	E[v - 1].append((u - 1, w))
	edges.append((u - 1, v - 1, w))
routes = []
for _ in range(k):
	(a, b) = map(int, input().split())
	routes.append((a - 1, b - 1))

def dijkstra(st):
	(pq, dist) = ([(0, st)], [float('inf') if i != st else 0 for i in range(n)])
	while len(pq) > 0:
		(d, u) = heapq.heappop(pq)
		if d != dist[u]:
			continue
		for (v, w) in E[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist
dist = []
for i in range(n):
	dist.append(dijkstra(i))
ans = float('inf')
for (u, v, _) in edges:
	now = 0
	for (a, b) in routes:
		now += min(dist[a][b], dist[a][u] + dist[b][v], dist[a][v] + dist[b][u])
	ans = min(ans, now)
print(ans)


def edge_input(m):
	l = [[] for i in range(n)]
	e = []
	for i in range(m):
		(c1, c2, cost) = map(int, input().split())
		c1 -= 1
		c2 -= 1
		l[c1].append((c2, cost))
		l[c2].append((c1, cost))
		e.append((c1, c2))
	return (l, e)
(n, m, k) = map(int, input().split())
(l, e) = edge_input(m)
quries = []
for i in range(k):
	(q1, q2) = map(int, input().split())
	q1 -= 1
	q2 -= 1
	quries.append([q1, q2])
import heapq

def dijkstra(x, l, n):
	v = [False] * n
	distance = [float('inf')] * n
	distance[x] = 0
	heap = [(0, x)]
	heapq.heapify(heap)
	while len(heap) != 0:
		(w, temp) = heapq.heappop(heap)
		if not v[temp]:
			v[temp] = True
			for (node, c) in l[temp]:
				if distance[temp] + c < distance[node]:
					distance[node] = distance[temp] + c
					heapq.heappush(heap, (distance[node], node))
	return distance
d = []
for i in range(n):
	d.append(dijkstra(i, l, n))
ans = float('inf')
for (v1, v2) in e:
	cur = 0
	for (a, b) in quries:
		cur += min(d[a][b], d[a][v1] + d[v2][b], d[a][v2] + d[v1][b])
	ans = min(ans, cur)
print(ans)


import heapq
(n, m, k) = map(int, input().split())
G = [[] for i in range(n)]
Edges = []
for i in range(m):
	(x, y, w) = map(int, input().split())
	G[x - 1].append((w, y - 1))
	G[y - 1].append((w, x - 1))
	Edges.append((x - 1, y - 1))
paths = [tuple(map(int, input().split())) for i in range(k)]
inf = 1 << 30
ans = inf
shortestpath = []
que = []
heapq.heapify(que)
for s in range(n):
	d = [inf] * n
	d[s] = 0
	heapq.heappush(que, (0, s))
	while que:
		(cost, node) = heapq.heappop(que)
		if cost > d[node]:
			continue
		for (w, p) in G[node]:
			if d[p] > d[node] + w:
				d[p] = d[node] + w
				heapq.heappush(que, (d[p], p))
	shortestpath.append(d)
for (s, t) in Edges:
	subcost = 0
	for (a, b) in paths:
		a -= 1
		b -= 1
		subcost += min(shortestpath[a][b], shortestpath[a][s] + shortestpath[t][b], shortestpath[a][t] + shortestpath[s][b])
	ans = min(ans, subcost)
print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
from heapq import *
inf = 10 ** 16
(n, m, k) = MI()
to = [[] for _ in range(n)]
uvw = []
for i in range(m):
	(u, v, w) = MI()
	(u, v) = (u - 1, v - 1)
	to[u].append((v, w))
	to[v].append((u, w))
	uvw.append((u, v, w))
sg = LLI1(k)
cost = [[inf] * n for _ in range(n)]
for su in range(n):
	hp = []
	heappush(hp, (0, su))
	cost[su][su] = 0
	while hp:
		(c, u) = heappop(hp)
		if c > cost[su][u]:
			continue
		for (v, w) in to[u]:
			nc = c + w
			if nc >= cost[su][v]:
				continue
			cost[su][v] = nc
			heappush(hp, (nc, v))
ans = inf
for (u, v, w) in uvw:
	cur = 0
	for (s, g) in sg:
		cur += min(cost[s][g], cost[s][u] + cost[v][g], cost[s][v] + cost[u][g])
	ans = min(ans, cur)
print(ans)


from sys import stdin
input = stdin.readline
from heapq import heappush, heappop
(n, m, k) = map(int, input().split())
r = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
adj = [[] for _ in range(n + 1)]
for (u, v, w) in r[:m]:
	adj[u].append([v, w])
	adj[v].append([u, w])
INF = 10 ** 9
dis = [[INF] * (n + 1) for _ in range(n + 1)]
for s in range(1, n + 1):
	dis[s][s] = 0
	h = [(0, s)]
	while h:
		(curd, cur) = heappop(h)
		if curd > dis[s][cur]:
			continue
		for (nxt, w) in adj[cur]:
			nd = curd + w
			if nd < dis[s][nxt]:
				dis[s][nxt] = nd
				heappush(h, (nd, nxt))
res = INF
for (s, e, _) in r[:m]:
	temp = 0
	for (cs, ce) in r[m:]:
		temp += min(dis[cs][ce], dis[cs][s] + dis[ce][e], dis[cs][e] + dis[ce][s])
	res = min(res, temp)
print(res)


from heapq import heappush, heappop
import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def dijkstra(adj: list, start: int, dists, inf: int=10 ** 8) -> list:
	v_count = len(adj)
	dists[start] = 0
	(geta, mask) = (10, (1 << 10) - 1)
	(hq, rem) = ([start], v_count - 1)
	while hq and rem:
		x = heappop(hq)
		(cost, src) = (x >> geta, x & mask)
		if dists[src] < cost:
			continue
		rem -= 1
		for (dest, e_cost) in adj[src]:
			if dists[dest] > cost + e_cost:
				dists[dest] = cost + e_cost
				heappush(hq, (cost + e_cost << geta) + dest)
	return dists

def main():
	(n, m, k) = map(int, input().split())
	adj = [[] for _ in range(n)]
	edges = []
	for (u, v, w) in (map(int, input().split()) for _ in range(m)):
		adj[u - 1].append((v - 1, w))
		adj[v - 1].append((u - 1, w))
		edges.append((u - 1, v - 1))
	route = []
	for (a, b) in (map(int, input().split()) for _ in range(k)):
		route.append((a - 1, b - 1) if a < b else (b - 1, a - 1))
	ans = inf = 10 ** 9 + 100
	dist = [array('i', [inf]) * n for _ in range(n)]
	for (a, b) in route:
		if a > b:
			(a, b) = (b, a)
		if dist[a][a] == inf:
			dijkstra(adj, a, dist[a], inf)
	for (u, v) in edges:
		if dist[u][u] == inf:
			dijkstra(adj, u, dist[u], inf)
		if dist[v][v] == inf:
			dijkstra(adj, v, dist[v], inf)
		cost = 0
		for (a, b) in route:
			cost += min(dist[u][a] + dist[v][b], dist[u][b] + dist[v][a], dist[a][b])
		ans = min(ans, cost)
	print(ans)
main()


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from heapq import heappush, heappop

def dijkstra(E, start):
	N = len(E)
	inf = 1 << 30
	dist = [inf] * N
	dist[start] = 0
	q = [start]
	mask = (1 << 10) - 1
	while q:
		p = heappop(q)
		(dist_v, v) = (p >> 10, p & mask)
		if dist[v] != dist_v:
			continue
		for (u, dist_vu) in E[v].items():
			dist_u = dist_v + dist_vu
			if dist_u < dist[u]:
				dist[u] = dist_u
				heappush(q, dist_u << 10 | u)
	return dist
(N, M, K) = map(int, input().split())
E = [{} for _ in range(1 + N)]
edges = []
for _ in range(M):
	(x, y, z) = map(int, input().split())
	edges.append((x, y, z))
	if y in E[x]:
		if z < E[x][y]:
			E[x][y] = z
			E[y][x] = z
	else:
		E[x][y] = z
		E[y][x] = z
AB = [list(map(int, input().split())) for _ in range(K)]
Dist0 = []
for (a, b) in AB:
	d = dijkstra(E, a)[b]
	Dist0.append(d)
ans = 1 << 61
for (x, y, z) in edges:
	tmp = E[x][y]
	E[x][y] = 0
	E[y][x] = 0
	dist = dijkstra(E, x)
	an = 0
	for (d0, (a, b)) in zip(Dist0, AB):
		d = dist[a] + dist[b]
		an += d0 if d0 < d else d
	if ans > an:
		ans = an
	E[x][y] = tmp
	E[y][x] = tmp
print(ans)


import sys
input = sys.stdin.readline
import heapq

def dijkstra(n, s, edges):
	hq = [(0, s)]
	cost = [float('inf')] * n
	cost[s] = 0
	while hq:
		(c, v) = heapq.heappop(hq)
		if c > cost[v]:
			continue
		for (d, u) in edges[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

def main():
	(n, m, k) = map(int, input().split())
	edges = [[] for _ in range(n)]
	xy = []
	for _ in range(m):
		(x, y, t) = map(int, input().split())
		x -= 1
		y -= 1
		edges[x].append((t, y))
		edges[y].append((t, x))
		xy.append((x, y))
	dist = [[] for _ in range(n)]
	for i in range(n):
		dist[i] = dijkstra(n, i, edges)
	ab = [list(map(int, input().split())) for _ in range(k)]
	ans = 10 ** 20
	for (x, y) in xy:
		tmp = 0
		for (a, b) in ab:
			a -= 1
			b -= 1
			tmp += min(dist[a][b], dist[a][x] + dist[b][y], dist[a][y] + dist[b][x])
		ans = min(ans, tmp)
	print(ans)
main()


import os, sys, bisect
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')
input = lambda : sys.stdin.readline().strip()
imap = lambda : map(int, input().split())
ilist = lambda : list(imap())
mod = int(1000000000.0 + 7)
from heapq import heapify, heappop as pop, heappush as push
(n, m, k) = imap()
gr = defaultdict(list)
for i in range(m):
	(x, y, w) = imap()
	gr[x].append([y, w])
	gr[y].append([x, w])
couriers = []
for i in range(k):
	couriers.append(ilist())
dist = [[float('inf')] * (n + 1) for i in range(n + 1)]

def shortestPath(s):
	q = [(0, s)]
	heapify(q)
	dist[s][s] = 0
	while q:
		(wt, cur) = pop(q)
		for (i, w) in gr[cur]:
			nwt = w + wt
			if nwt < dist[s][i]:
				dist[s][i] = nwt
				push(q, (nwt, i))
for i in range(1, n + 1):
	shortestPath(i)
res = float('inf')
for i in range(1, n + 1):
	for (j, _) in gr[i]:
		cost = 0
		for (u, v) in couriers:
			cost += min(dist[u][v], dist[u][i] + dist[j][v], dist[u][j] + dist[i][v])
		res = min(res, cost)
print(res)


import time
start_time = time.time()

def TIME_():
	print(time.time() - start_time)
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
BIG = 10 ** 9

def solve():
	(N, M, K) = getInts()
	G = [[] for _ in range(N)]
	edges = []
	for j in range(M):
		(x, y, w) = getInts()
		x -= 1
		y -= 1
		G[x].append((y, w))
		G[y].append((x, w))
		edges.append((x, y))

	def DK(u):
		Q = [(0, u)]
		D = [BIG] * N
		D[u] = 0
		while Q:
			(d, u) = h.heappop(Q)
			if d > D[u]:
				continue
			for (v, w) in G[u]:
				new_d = w + D[u]
				if new_d < D[v]:
					D[v] = new_d
					h.heappush(Q, (new_d, v))
		return D
	dist = [DK(i) for i in range(N)]
	routes = [tuple(getInts()) for _ in range(K)]
	ans = 10 ** 18
	for (x, y) in edges:
		curr = 0
		for (a, b) in routes:
			a -= 1
			b -= 1
			curr += min(dist[a][b], dist[a][x] + dist[y][b], dist[a][y] + dist[x][b])
		ans = min(ans, curr)
	return ans
print(solve())


import sys
input = sys.stdin.readline
from collections import defaultdict
from math import inf
from heapq import heappop, heappush

def dijkstra(start):
	(heap, dist) = ([(0, start)], [inf] * (n + 1))
	dist[start] = 0
	while heap:
		(d, vertex) = heappop(heap)
		for (child, weight) in graph[vertex]:
			weight += d
			if dist[child] > weight:
				dist[child] = weight
				heappush(heap, (weight, child))
	return dist
(n, m, k) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
weights = defaultdict(int)
connectlist = []
for i in range(m):
	(a, b, w) = map(int, input().split())
	graph[a].append((b, w))
	graph[b].append((a, w))
	connectlist.append((a, b))
route = []
distlist = []
for i in range(n):
	distlist.append(dijkstra(i + 1))
for i in range(k):
	(src, dst) = map(int, input().split())
	route.append((src, dst))
ans = 10 ** 10
for i in connectlist:
	tmp = 0
	for j in route:
		tmp += min(distlist[j[0] - 1][j[1]], distlist[j[0] - 1][i[0]] + distlist[j[1] - 1][i[1]], distlist[j[0] - 1][i[1]] + distlist[j[1] - 1][i[0]])
	if tmp < ans:
		ans = tmp
print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict
sys.setrecursionlimit(300000)

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def solve():
	(n, m, Q) = sep()
	inf = float('inf')
	g = [[] for _ in range(n + 1)]
	edges = []
	for _ in range(m):
		(a, b, c) = sep()
		g[a].append((b, c))
		g[b].append((a, c))
		edges.append((a, b))
	Distance = [[inf] * (n + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		Distance[i][i] = 0
	for i in range(1, n + 1):
		q = [(0, i)]
		heapify(q)
		while q:
			(d, v1) = heappop(q)
			for t in g[v1]:
				(v2, c) = t
				if Distance[i][v2] > d + c:
					Distance[i][v2] = d + c
					heappush(q, (d + c, v2))
	mi = 999999999999999999999
	queries = [tuple(sep()) for _ in range(Q)]
	for i in edges:
		(x, y) = i
		ans = 0
		for j in queries:
			(fr, to) = j
			ans += min(Distance[fr][to], Distance[fr][x] + Distance[y][to], Distance[x][to] + Distance[y][fr])
		mi = min(ans, mi)
	print(mi)
solve()


import os, sys
from io import BytesIO, IOBase
from heapq import *

def short(n, path, st):
	visi = [0] * n
	dist = [10 ** 20] * n
	dist[st] = 0
	he = [(0, st)]
	heapify(he)
	while len(he):
		x = heappop(he)[1]
		if visi[x]:
			continue
		visi[x] = 1
		for yy in path[x]:
			(i, j) = yy
			if visi[i]:
				continue
			if dist[i] > dist[x] + j:
				dist[i] = dist[x] + j
				heappush(he, (dist[i], i))
	return dist

def main():
	(n, m, k) = map(int, input().split())
	path = [[] for _ in range(n)]
	edg = []
	for _ in range(m):
		(u1, v1, c1) = map(int, input().split())
		edg.append((u1 - 1, v1 - 1, c1))
		path[u1 - 1].append((v1 - 1, c1))
		path[v1 - 1].append((u1 - 1, c1))
	dist = [short(n, path, i) for i in range(n)]
	route = [tuple(map(lambda xx: int(xx) - 1, input().split())) for _ in range(k)]
	ans = 0
	for i in route:
		ans += dist[i[0]][i[1]]
	for i in edg:
		ans1 = 0
		for j in route:
			ans1 += min(dist[j[0]][i[0]] + dist[i[1]][j[1]], dist[j[0]][i[1]] + dist[i[0]][j[1]], dist[j[0]][j[1]])
		ans = min(ans, ans1)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
(N, M, K) = map(int, input().split())
e = [[] for _ in range(N + 1)]
for _ in range(M):
	(u, v, c) = map(int, input().split())
	e[u].append((v, c))
	e[v].append((u, c))
qs = [tuple(map(int, input().split())) for _ in range(K)]
import heapq
hpush = heapq.heappush
hpop = heapq.heappop

class dijkstra:

	def __init__(self, n, e):
		self.e = e
		self.n = n

	def path(self, s):
		d = [float('inf')] * (self.n + 1)
		vis = [0] * (self.n + 1)
		d[s] = 0
		h = [s]
		while len(h):
			v = hpop(h)
			v1 = v % 10 ** 4
			v0 = v // 10 ** 4
			if vis[v1]:
				continue
			vis[v1] = 1
			for p in self.e[v1]:
				d[p[0]] = min(d[p[0]], d[v1] + p[1])
				if vis[p[0]]:
					continue
				hpush(h, d[p[0]] * 10 ** 4 + p[0])
		return d
dij = dijkstra(N, e)
ps = [[]]
for x in range(1, N + 1):
	ps.append(dij.path(x))
t = [ps[qs[i][0]][qs[i][1]] for i in range(K)]
res = sum(t)
for x in range(1, N + 1):
	ps.append(dij.path(x))
for x in range(1, N + 1):
	for (y, c) in e[x]:
		tt = t[:]
		for k in range(K):
			tt[k] = min(tt[k], ps[x][qs[k][0]] + ps[y][qs[k][1]], ps[y][qs[k][0]] + ps[x][qs[k][1]])
		res = min(res, sum(tt))
print(res)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
import heapq
(n, m, k) = map(int, input().split())
edgeList = []
edges = [[] for _ in range(n)]
for _ in range(m):
	edge = tuple(map(int, input().split()))
	edge = (edge[0] - 1, edge[1] - 1, edge[2])
	edgeList.append(edge)
	edges[edge[0]].append((edge[1], edge[2]))
	edges[edge[1]].append((edge[0], edge[2]))
routes = []
for _ in range(k):
	route = list(map(int, input().split()))
	routes.append((route[0] - 1, route[1] - 1))
minCosts = [[float('inf')] * n for _ in range(n)]
for i in range(n):
	minCosts[i][i] = 0
	pq = [(0, i)]
	visited = [False] * n
	while pq:
		(cost, u) = heapq.heappop(pq)
		if visited[u]:
			continue
		visited[u] = True
		for (v, w) in edges[u]:
			if minCosts[i][v] > cost + w:
				minCosts[i][v] = cost + w
				heapq.heappush(pq, (cost + w, v))
minTotal = float('inf')
for edge in edgeList:
	total = 0
	for route in routes:
		total += min(minCosts[route[0]][route[1]], minCosts[route[0]][edge[0]] + minCosts[edge[1]][route[1]], minCosts[route[0]][edge[1]] + minCosts[edge[0]][route[1]])
	minTotal = min(total, minTotal)
print(str(minTotal))


def edge_input(m):
	l = [[] for i in range(n)]
	e = []
	for i in range(m):
		(c1, c2, cost) = map(int, input().split())
		c1 -= 1
		c2 -= 1
		l[c1].append((c2, cost))
		l[c2].append((c1, cost))
		e.append((c1, c2))
	return (l, e)
(n, m, k) = map(int, input().split())
(l, e) = edge_input(m)
quries = []
for i in range(k):
	(q1, q2) = map(int, input().split())
	q1 -= 1
	q2 -= 1
	quries.append([q1, q2])
import heapq

def finddist(s, g, n):
	d = [10 ** 10] * n
	handled = [False] * n
	d[s] = 0
	heap = [(0, s)]
	heapq.heapify(heap)
	while len(heap) > 0:
		(l, v) = heapq.heappop(heap)
		if not handled[v]:
			handled[v] = True
			for (nextV, w) in g[v]:
				if d[nextV] > d[v] + w:
					d[nextV] = d[v] + w
					heapq.heappush(heap, (d[nextV], nextV))
	return d
d = []
for i in range(n):
	d.append(finddist(i, l, n))
ans = float('inf')
for (v1, v2) in e:
	cur = 0
	for (a, b) in quries:
		cur += min(d[a][b], d[a][v1] + d[v2][b], d[a][v2] + d[v1][b])
	ans = min(ans, cur)
print(ans)


import sys
inp = sys.stdin.buffer.readline
inar = lambda : list(map(int, inp().split()))
inin = lambda : int(inp())
inst = lambda : inp().decode().strip()
wrt = sys.stdout.write
pr = lambda *args, end='\n': wrt(' '.join([str(x) for x in args]) + end)
enum = enumerate
inf = float('inf')
cdiv = lambda x, y: -(-x // y)
mod = 1000000007
from heapq import heappop, heappush

def dijkstra(n, graph, start):
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)
_T_ = 1
for _t_ in range(_T_):
	(n, m, k) = inar()
	gr = [[] for i in range(n)]
	paths = []
	for i in range(m):
		(u, v, w) = inar()
		u -= 1
		v -= 1
		gr[u].append((v, w))
		gr[v].append((u, w))
	routes = []
	for i in range(k):
		(a, b) = inar()
		routes.append((a - 1, b - 1))
	dist = [[] for i in range(n)]
	for i in range(n):
		(dist[i], _) = dijkstra(n, gr, i)
	ans = inf
	for a in range(n):
		for (b, w) in gr[a]:
			cur = 0
			for (x, y) in routes:
				cur += min(dist[x][y], dist[x][a] + dist[b][y], dist[x][b] + dist[a][y])
			ans = min(ans, cur)
	pr(ans)


import io
import os
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush
inf = float('inf')

def solve(N, M, K, U, V, W, routes):
	graph = [[] for i in range(N)]
	for (u, v, w) in zip(U, V, W):
		graph[u].append((v, w))
		graph[v].append((u, w))

	def dijkstra(source):
		dist = [inf] * N
		queue = []
		heappush(queue, (0, source))
		while queue:
			(minDist, minNode) = heappop(queue)
			if dist[minNode] <= minDist:
				continue
			dist[minNode] = minDist
			for (nbr, weight) in graph[minNode]:
				if minDist + weight < dist[nbr]:
					heappush(queue, (minDist + weight, nbr))
		return dist
	dists = []
	for u in range(N):
		dists.append(dijkstra(u))
	best = inf
	for (u, v) in zip(U, V):
		total = 0
		for (a, b) in routes:
			distA = dists[a]
			distB = dists[b]
			assert distA[b] == distB[a]
			cost = distA[b]
			total += min(cost, distA[u] + distB[v], distA[v] + distB[u])
		best = min(best, total)
	return best
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N, M, K) = [int(x) for x in input().split()]
	U = []
	V = []
	W = []
	for i in range(M):
		(u, v, w) = [int(x) for x in input().split()]
		u -= 1
		v -= 1
		U.append(u)
		V.append(v)
		W.append(w)
	routes = [[int(x) - 1 for x in input().split()] for i in range(K)]
	ans = solve(N, M, K, U, V, W, routes)
	print(ans)


from math import inf
import heapq
(n, m, k) = map(int, input().split())
G = [[] for _ in range(n)]
Q = []
for _ in range(m):
	(x, y, w) = map(int, input().split())
	G[x - 1].append((y - 1, w))
	G[y - 1].append((x - 1, w))
for _ in range(k):
	(a, b) = map(int, input().split())
	Q.append((a - 1, b - 1))

def solve(x):
	dist = [inf] * n
	dist[x] = 0
	q = [(0, x)]
	while q:
		(d, x) = heapq.heappop(q)
		for (y, w) in G[x]:
			if d + w < dist[y]:
				dist[y] = d + w
				heapq.heappush(q, (d + w, y))
	return dist
D = [solve(x) for x in range(n)]
ans = inf
for x in range(n):
	for (y, w) in G[x]:
		s = 0
		for (a, b) in Q:
			v = min(D[a][x] + D[y][b], D[a][y] + D[x][b], D[a][b])
			s += v
		ans = min(s, ans)
print(ans)


import os
import sys
from io import BytesIO, IOBase
from heapq import heappop, heappush

def dijkstra(n, graph, start):
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)

def main():
	(n, m, k) = map(int, input().split())
	adjacencyList = []
	connectionList = []
	for _ in range(n):
		adjacencyList.append([])
	for _ in range(m):
		(x, y, d) = map(int, input().split())
		adjacencyList[x - 1].append((y - 1, d))
		adjacencyList[y - 1].append((x - 1, d))
		connectionList.append((x - 1, y - 1))
	routeList = []
	for _ in range(k):
		routeList.append(tuple(map(lambda x: x - 1, map(int, input().split()))))
	distList = []
	for i in range(n):
		(dist, parents) = dijkstra(n, adjacencyList, i)
		distList.append(dist)
	minAns = 10 ** 10
	for connection in connectionList:
		curAns = 0
		for route in routeList:
			curAns += min(distList[route[0]][route[1]], distList[route[0]][connection[0]] + distList[route[1]][connection[1]], distList[route[1]][connection[0]] + distList[route[0]][connection[1]])
		if curAns < minAns:
			minAns = curAns
	print(minAns)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()