n, m, q = map(int, input().split())
edges = {}
for i in range(m):
    a, b, w = map(int, input().split())
    if a == b:
        continue

    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)


dis = [[0x7fffffff]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dis[i][i] = 0
for (a, b), w in edges.items():
    dis[a][b] = w


for t in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            dis[a][b] = min(dis[a][b], dis[a][t] + dis[t][b], 0x7fffffff)
            if dis[a][b] >= 0x7fffffff // 2:
                dis[a][b] = 0x7fffffff

for _ in range(q):
    a, b = map(int, input().split())
    print('impossible' if dis[a][b] == 0x7fffffff else dis[a][b])