// 给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
//
// 再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。
//
// 数据保证图中不存在负权回路。
//
// 输入格式
// 第一行包含三个整数n，m，k
//
// 接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
//
// 接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。
//
// 输出格式
// 共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。
//
package main

import(
    "fmt"
    "bufio"
    "os"
)

const N=210 // 1≤n≤200,
const K=N*N // 1≤k≤n2
const M=20010 // 1≤m≤20000,

// 图中涉及边长绝对值均不超过10000。
const Max=10000*N*2 // 最大距离, 统计后的距离小于 Max/2 为可达距离

var(
    reader = bufio.NewReader(os.Stdin)
    writer = bufio.NewWriter(os.Stdout)

    n,m,k int
    x,y,z int
    dist [N][N]int // 邻接矩阵，节点距离存储
)

// 动态规划思想，用邻接矩阵存储所有边，嵌套三层循环，循环所有点，
// 计算 `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`，
// 公式的意义是计算 i和j之间经过k节点的距离是不是会更短。 
// `dist[i][j]` 一开始存的是边的距离，通过动态规划计算后变成了任意两点i和j之间的最短距离。
func floyd() {
   for t:=1;t<=n;t++{
       for i:=1;i<=n;i++{
           for j:=1;j<=n;j++{
               if dist[i][j] > dist[i][t] + dist[t][j] {
                   dist[i][j] = dist[i][t] + dist[t][j]
               }
           }
       }
   }
}


func main(){
    fmt.Fscan(reader, &n, &m, &k)

    // 初始化为最大值
    for i:=1;i<=n;i++{
        dist[1][i] = Max
    }
    for i:=2;i<=n;i++{
        // 使用copy初始化后面行，效率更高
        copy(dist[i][:] , dist[1][:])
    }
    for i:=1;i<=n;i++{
        // 对角线，点自己到自己距离为0
        dist[i][i] = 0
    }

    for i:=0;i<m;i++{
        fmt.Fscan(reader, &x,&y,&z)
        // 忽略自环
        if x==y {
            continue
        }
        // 重边指定为最小的边
        if dist[x][y] > z {
            dist[x][y] = z
        }
    }

    floyd()

    for i:=0;i<k;i++{
        fmt.Fscan(reader, &x,&y)
        if dist[x][y] > Max/2 {
            fmt.Fprintln(writer, "impossible")
        }else{
            fmt.Fprintln(writer, dist[x][y])
        }
    }
    writer.Flush()
}