//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def Floyd():
    # k = i = j = 1 # !!!大错误，应该将每个遍历变量的初始化放在循环内，而不是循环外
    # while k<=n:
    #     while i<=n:
    #         while j<=n:
    #             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    #             j+= 1
    #         i+= 1
    #     k+= 1
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    N = 210
    # dist存储i到j的最短距离
    dist = [[float('inf')]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j: dist[i][j] = 0
    for i in range(1, m+1):
        x, y, z = map(int, input().split())
        dist[x][y] = min(dist[x][y], z)
    Floyd()
    for i in range(q):
        x, y = map(int, input().split())
        print('impossible' if dist[x][y] == float('inf') else dist[x][y])

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def Prim():
    """
    返回最小生成树的最短距离
    遍历n个点放入集合，每次更新集合外的点到集合的最短距离
    """
    res = 0
    for i in range(n):
        t = -1
        # 找到距离集合最近的点
        for j in range(1, n+1):
            if not st[j] and (t == -1 or dist[t]>dist[j]): t = j
        # 当集合最近的点不连通时，失败
        if i and dist[t] == float('inf'): return 'impossible'
        # 将最近点放入集合
        st[t] = True
        # 如果不是第一个点，将结果加上最短距离
        if i: res += dist[t]
        # 更新集合外所有点到集合的距离，注意要先计算结果，否则可能负环会把距离更新掉
        for j in range(1, n+1): dist[j] = min(dist[j], g[t][j])
        return res
if __name__ == '__main__':
    n, m = map(int, input().split())
    N = 510
    # 存储所有的边
    g = [[float('inf')]*N for i in range(N)]
    # 存储集合外的点到集合的最短距离
    dist = [float('inf')]*N
    st = [False]*N
    for i in range(m):
        a, b, c = map(int, input().split())
        g[a][b] = g[b][a] = min(g[a][b], c)
    print(Prim())

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import heapq
def spfa_ring():
    """
    寻找负权回路
    """
    cont = [0]*N    #存储跟新后节点的最小距离的边数，可以不用初始化
    heap = []
    # 将所有节点入队，防止负权回路存在于非连通域
    for i in range(1,n+1):
        heapq.heappush(heap, i)
    while len(heap):
        t = heapq.heappop(heap)
        st[t] = False
        i = h[t]
        while i!= -1:
            node = e[i]
            if dist[node] > dist[t] + w[i]:
                dist[node] = dist[t] + w[i]
                cont[node] = cont[t] + 1
                # 根据抽屉原理，当节点的最短距离大于等于n时，存在负权回路
                if cont[node] >= n: return True
                # 将有限序列中不存在的节点推入
                if not st[node]:
                    heapq.heappush(heap, node)
                    st[node] = True
            i = ne[i]
    return False
if __name__ == '__main__':
    n, m = map(int, input().split())
    N = 100010
    h, ne, e = [[-1]*N for i in range(3)]
    idx = 0
    # ！！！注意：这里绝对不同用float("inf"),因为在比较dist距离时，dist[t]+w还是==float("inf")，因此不能更新距离
    w, dist = [[0]*N for i in range(2)]
    dist[1] = 0
    st = [True]*N
    for i in range(m):
        a, b, c = map(int, input().split())
        e[idx] = b
        ne[idx] = h[a]
        h[a] = idx
        w[idx] = c
        idx += 1
    print('Yes' if spfa_ring() else 'No')

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import heapq
def spfa():
    """
    堆优化的bellman_ford算法，在不存在负权回路时可以适用。
    复杂度最好为O（n),最坏为O（nm）
    只有节点有更新时，遍历其每一条边
    """
    heap = []
    heapq.heappush(heap, 1)
    st[1] = True
    while len(heap):
        t = heapq.heappop(heap)
        st[t] = False
        i = h[t]
        while i!= -1:
            node = e[i]
            if dist[node] > dist[t] + w[i]:
                dist[node] = dist[t] + w[i]
                # 将有限序列中不存在的节点推入
                if not st[node]:
                    heapq.heappush(heap, node)
                    st[node] = True
            i = ne[i]
    return 'impossible' if dist[n] == float('inf') else dist[n]
if __name__ == '__main__':
    n, m = map(int, input().split())
    N = 100010
    h, ne, e = [[-1]*N for i in range(3)]
    idx = 0
    w, dist = [[float('inf')]*N for i in range(2)]
    dist[1] = 0
    st = [False]*N
    for i in range(m):
        a, b, c = map(int, input().split())
        e[idx] = b
        ne[idx] = h[a]
        h[a] = idx
        w[idx] = c
        idx += 1
    print(spfa())

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def Bellman_ford():
    只有上一次迭代中松驰过的点才能参加下一次迭代的松弛操作
    for i in range(k):
        # 有边数限制的最短路时，一定要进行备份，更新时和上一次迭代的结果相比较，防止遍历时出现串联问题
        # 如果不使用备份数组，允许串联式更新，那么第k次更新的最短路上边的数量至少是 k
        # 限制这个点只能用上一个结点迭代的结果
        backup = dist[::]
        for j in range(m):
            a, b, w = edges[j]
            # 遍历所有的边，每次迭代最少更新一个点的最短距离。
            # 若第n此迭代仍能更新，根据抽屉原理说明至少存在一条负权回路，可以用来判断负权边
            if dist[b]>backup[a] + w: dist[b] = backup[a] + w
    return 'impossible' if dist[n] == float('inf') else dist[n]

if __name__ == '__main__':
    n, m, k = map(int, input().split())
    # 存储图中所有的边
    edges = [tuple(map(int, input().split())) for i in range(m)]
    dist = [float('inf')]*(n+10)
    dist[1] = 0
    print(Bellman_ford())

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import heapq


def dijstra_heap():
    # 初始化1到起点的距离为0，并将0，1 压入队列作为循环起点
    dist[1] = 0
    heapq.heappush(heap, (0, 1))
    while len(heap):
        t = heapq.heappop(heap)
        node = t[1]
        dis = t[0]
        # 若节点到起点的最小距离未确定，那么更新其所有邻接点的距离
        if st[node]: continue
        st[node] = True
        j = h[node]
        while j != -1:
            i = e[j]
            # 如果邻接点的距离大于节点的距离+边的长度，那么更新这个距离，并压入队列
            if dis + w[j] < dist[i]:
                dist[i] = dis + w[j]
                heapq.heappush(heap, (dist[i], i))
            j = ne[j]
    return -1 if dist[n] == float('inf') else dist[n]


if __name__ == '__main__':
    # 根据n,m的范围确定时稀疏图，用邻接表存储
    n, m = map(int, input().split())
    N = 150010
    h, e, ne = [-1] * N, [-1] * N, [-1] * N
    # w存储边的长度
    w = [float('inf')] * N
    idx = 0
    st = [False] * N
    dist = [float('inf')] * N
    # heap优先队列存储节点和其到起点的距离
    heap = []
    for i in range(m):
        a, b, c = map(int, input().split())
        e[idx] = b
        ne[idx] = h[a]
        h[a] = idx
        w[idx] = c
        idx += 1
    print(dijstra_heap())

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def dijstra():
    """
    遍历n个节点，找到其中距离起点最短的点，然后更新所有点的距离。时间复杂度O（n**2+m)
    """
    for i in range(n):
        # t作为每次寻找最小距离点的起始位置。-1而不是0，我的理解是，为了防止节点的下标从0开始，-1比较方便适用2种情况
        t = -1 
        for j in range(1, n+1):
            if st[j] == 0 and (t == -1 or dist[j]<dist[t]):
                t = j
        st[t]  = 1
        # 更新所有点的距离，取当前点到t的距离和t到起点距离和，与起点到当前点距离的最小值
        for k in range(1, n+1):
            dist[k] = min(dist[k], dist[t] + g[t][k])
    if dist[n] == float('inf'): return -1
    else: return dist[n]        


if __name__ == '__main__':
    n, m = map(int, input().split())
    N  = 510
    # 稠密图用邻接矩阵存储，因为可能有重边，初始值设为无穷大
    g = [[float('inf')]*N for i in range(N)] 
    # 存储节点的最短路径是否已经确定  
    st = [0]*N
    # 存储每个节点到起点的最短路径
    dist = [float('inf')]*N
    # 设1为起点
    dist[1] = 0
    for i in range(m):
        a, b, c = map(int, input().split())
        # 若存在重边，取较小的边
        g[a][b] = min(g[a][b], c)
    print(dijstra())

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#  拓扑排序答案不唯一
# 有向无环图至少存在一个拓扑序列
# 根据每个节点的入度来判断是否入队

def topsort():
    """
    返回是否存在拓扑排序
    """
    hh = 0
    tt = -1
    for i in range(1, n + 1):
        # 入度为0的点入队，作为起点
        if d[i] == 0:
            tt += 1
            q[tt] = i
    while hh <= tt:
        t = q[hh]
        hh += 1
        i = h[t]
        # 遍历队首的每一个邻接点
        while i != -1:
            j = e[i]
            # 每访问一个元素，其入度减一
            d[j] -= 1
            # 若入度为0则入队
            if d[j] == 0:
                tt += 1
                q[tt] = j
            i = ne[i]
    # 若所有元素都入队，那么存在拓扑
    return tt == n - 1


def ins(a, b):
    """
    邻接表
    """
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1


if __name__ == '__main__':
    n, m = map(int, input().split())
    N = 100010
    e = [-1] * N
    h = [-1] * N
    ne = [-1] * N
    idx = 0
    q = [0] * n   
    d = [0] * N
    for i in range(m):
        a, b = map(int, input().split())
        ins(a, b)
        d[b] += 1      # 记录每个点的入度
    if topsort():
        print(' '.join(map(str, q)))
    else:
        print('-1')

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def dfs(x):
    """
    x的子树中点的数量
    """
    global ans      # 存储重心的最大节点数，即最大点数的最小值
    st[x] = True       # 标注当前点已经被搜索过
    su = 1  #存储以x为根的节点数，包括x
    res = 0 #存储删除掉节点x后，剩余连通域的最大节点数
    i = h[x]
    while i != -1: # 访问当前x的第一个邻接点，如果其存在
        j = e[i]       # 第一个邻接点的图的编号
        if not st[j]:   # 如果邻接点未被访问过，那么对其进行递归
            s = dfs(j)
            res = max(res, s)
            su += s
        i = ne[i]    # 访问当前x的下一个邻接点，如果其存在
    res = max(res, n - su)
    ans = min(res, ans)
    return su


def insert(x, y):
    """
    将y节点插入单链表，父节点时x
    """
    global idx
    e[idx] = y
    ne[idx] = h[x]
    h[x] = idx
    idx += 1


if __name__ == '__main__':
    n = int(input().strip())
    N = 10010
    h = [-1] * N    # 存储每个点的单链表的头节点下标（e）,也就是第一个邻接点，链表中边的数量和图中边的数量相等，-1表示尾节点
    e = [0] * N * 2 #存储节点在图中的编号
    ne = [-1] * N * 2 # 存储邻接点的下一个邻接点的下标（e）
    idx = 0          # 链表中的新节点编号
    st = [False] * N
    ans = N
    for i in range(n - 1):
        x, y = map(int, input().split())
        # 单向图表示无向图
        insert(x, y)
        insert(y, x)
    dfs(1)
    print(ans)

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def bfs():
    """
    逐层遍历图中所有节点
    """
    q = [0] * N
    q[0] = 1         # 队列存储对应编号
    hh = 0
    tt = 0
    d = [-1] * N     # 存储对应编号和1之间的距离，初始点1的距离为0
    d[1] = 0
    while hh <= tt:   #队列不为空时，从1开始逐层遍历
        t = q[hh]      # 队头出队
        hh += 1
        i = h[t]
        while i != -1:  # 遍历队首的所有邻接点
            j = e[i]
            if d[j] == -1:   # 判断当前点是否被访问，未被访问则入队
                tt += 1
                q[tt] = j
                d[j] = d[t] + 1  # 刚入队的距离等于正在被访问的队首距离+1，
            i = ne[i]  # 前往下一个邻接点
    return d[n]      # 遍历图中所有点后打印n的距离


def ins(a, b):
    """
    邻接表
    """
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1


if __name__ == '__main__':
    N = 10010
    M = 2 * N
    e = [-1] * M
    h = [-1] * N
    idx = 0
    ne = [0] * M
    n, m = map(int, input().split())
    for i in range(m):
        a, b = map(int, input().split())
        ins(a, b)
    print(bfs())