CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque, defaultdict

import sys

input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    N, M = list(map(int, input().split()))
    INF = 10 ** 18
    Tree = defaultdict(lambda: [])
    for _ in range(M):
        p, q, c = list(map(int, input().split()))
        Tree[(p, c)].append(((q, c), 0))
        Tree[(q, c)].append(((p, c), 0))
        Tree[(p, c)].append(((p, 0), 0))
        Tree[(q, c)].append(((q, 0), 0))
        Tree[(p, 0)].append(((q, c), 1))
        Tree[(q, 0)].append(((p, c), 1))

    # print(Tree)
    # # print(Tree[12])

    # dist = [INF] * N
    dist = defaultdict(lambda: INF)

    def bfs01(x, r):
        # q = deque([(x, -1)])
        q = deque()
        q.append((x, r))
        dist[(x, r)] = 0
        while q:
            u, rail = q.popleft()
            # print(u, rail)
            for (nx_node, nx_rail), cost in Tree[(u, rail)]:
                d = dist[(u, rail)] + cost
                # print(nx_node, nx_rail, d, cost, dist[(nx_node, nx_rail)])
                if d < dist[(nx_node, nx_rail)]:
                    dist[(nx_node, nx_rail)] = d
                    if cost:
                        q.append((nx_node, nx_rail))
                    else:
                        q.appendleft((nx_node, nx_rail))

    bfs01(1, 0)
    # print(dist, dist[(N, 0)])
    if dist[(N, 0)] == INF:
        print((-1))
    else:
        print((dist[(N, 0)]))


if __name__ == "__main__":
    main()


# Optimized solution
from collections import deque, defaultdict

import sys

input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    N, M = list(map(int, input().split()))
    INF = 10 ** 9
    Tree = defaultdict(lambda: [])
    for _ in range(M):
        p, q, c = list(map(int, input().split()))
        Tree[(p, c)].append(((q, c), 0))
        Tree[(q, c)].append(((p, c), 0))
        Tree[(p, c)].append(((p, 0), 0))
        Tree[(q, c)].append(((q, 0), 0))
        Tree[(p, 0)].append(((q, c), 1))
        Tree[(q, 0)].append(((p, c), 1))

    # print(Tree)
    # # print(Tree[12])

    # dist = [INF] * N
    dist = defaultdict(lambda: INF)

    def bfs01(x, r):
        # q = deque([(x, -1)])
        q = deque()
        q.append((x, r))
        dist[(x, r)] = 0
        while q:
            u, rail = q.popleft()
            # print(u, rail)
            for (nx_node, nx_rail), cost in Tree[(u, rail)]:
                d = dist[(u, rail)] + cost
                # print(nx_node, nx_rail, d, cost, dist[(nx_node, nx_rail)])
                if d < dist[(nx_node, nx_rail)]:
                    dist[(nx_node, nx_rail)] = d
                    if cost:
                        q.append((nx_node, nx_rail))
                    else:
                        q.appendleft((nx_node, nx_rail))

    bfs01(1, 0)
    # print(dist, dist[(N, 0)])
    if dist[(N, 0)] == INF:
        print((-1))
    else:
        print((dist[(N, 0)]))


if __name__ == "__main__":
    main()
# Original solution
import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    costs = [10 ** 9] * n
    corporations = [set() for _ in range(n)]
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if costs[v] < d or e in corporations[v]:
            continue
        costs[v] = d
        corporations[v].add(e)
        for u, c in links[v]:
            if c == e:
                nd = d
                func = q.appendleft
            else:
                nd = d + 1
                func = q.append
            if costs[u] < nd or c in corporations[u]:
                continue
            costs[u] = nd
            func((nd, u, c))
    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [set() for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print((bfs01(0, n - 1, links)))


# Optimized solution
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            for c in links[v]:
                for u in links[v][c]:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print((bfs01(0, n - 1, links)))
# Original solution
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            q.extend((d + 1, u, c) for c, us in list(links[v].items()) for u in us if (u, c) not in visited)
        else:
            q.extendleft((d, u, e) for u in links[v][e] if (u, e) not in visited)
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print((bfs01(0, n - 1, links)))


# Optimized solution
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            q.extend((d + 1, u, c) for c in links[v] for u in links[v][c] if (u, c) not in visited)
        else:
            q.extendleft((d, u, e) for u in links[v][e] if (u, e) not in visited)
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print((bfs01(0, n - 1, links)))
# Original solution
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            q.extend((d + 1, u, c) for c in links[v] for u in links[v][c] if (u, c) not in visited)
        else:
            q.extendleft((d, u, e) for u in links[v][e] if (u, e) not in visited)
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print((bfs01(0, n - 1, links)))


# Optimized solution
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            lv = links[v]
            for c in lv:
                for u in lv[c]:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print((bfs01(0, n - 1, links)))
# Original solution
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            lv = links[v]
            for c in lv:
                for u in lv[c]:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print((bfs01(0, n - 1, links)))


# Optimized solution
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            for c in links[v]:
                for u in links[v][c]:
                    if (u, c) not in visited:
                        q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) not in visited:
                    q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = list(map(int, readline().split()))
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print((bfs01(0, n - 1, links)))
# Original solution
from collections import defaultdict
from heapq import *
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,m=MI()
to=defaultdict(list)
inf=10**9
dist=defaultdict(int)
home=[set() for _ in range(n)]
for u in range(n):dist[u,-1]=inf
for _ in range(m):
    u,v,c=MI1()
    to[u,c].append(v)
    to[v,c].append(u)
    home[u].add(c)
    home[v].add(c)
    dist[u,c]=dist[v,c]=inf

hp=[]
dist[0,-1]=0
heappush(hp,(0,0,-1))
while hp:
    d,u,c=heappop(hp)
    #print(d,u,c,hp,dist)
    if u==n-1:
        print(d)
        break
    if d>dist[u,c]:continue
    if c==-1:
        for nc in home[u]:
            if d+1<dist[u,nc]:
                dist[u,nc]=d+1
                heappush(hp,(d+1,u,nc))
    else:
        if d<dist[u,-1]:
            dist[u,-1]=d
            heappush(hp,(d,u,-1))
        for v in to[u,c]:
            if d>=dist[v,c]:continue
            dist[v,c]=d
            heappush(hp,(d,v,c))
else:
    print(-1)


# Optimized solution
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from collections import deque

def solve():
    dist = [inf] * len(to)
    q = deque()
    q.append((0, 0))
    dist[0] = 0
    while q:
        d, i = q.popleft()
        if d > dist[i]: continue
        if i < n:
            for j in to[i]:
                if dist[j] <= d + 1: continue
                dist[j] = d + 1
                q.append((d + 1, j))
        else:
            for j in to[i]:
                if j == n - 1:
                    print(dist[i])
                    exit()
                if dist[j] <= d: continue
                dist[j] = d
                q.appendleft((d, j))
    print(-1)

inf=10**9
n,m=MI()
to=[]
uctoi={}

for u in range(n):
    to.append([])
    uctoi[u,0]=u

for _ in range(m):
    u,v,c=MI()
    u,v=u-1,v-1
    if (u,c) not in uctoi:
        i=uctoi[u,c]=len(to)
        to.append([])
        to[i].append(u)
        to[u].append(i)
    else:i=uctoi[u,c]
    if (v,c) not in uctoi:
        j=uctoi[v,c]=len(to)
        to.append([])
        to[j].append(v)
        to[v].append(j)
    else:j=uctoi[v,c]
    to[i].append(j)
    to[j].append(i)
#print(to)
#print(fin)

solve()
# Original solution
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
n,m = list(map(int, input().split()))
link = defaultdict(list)
chg=10**8
for _ in range(m):
    p,q,c=list(map(int, input().split()))
    link[p].append([p+chg*c,1])
    link[p+chg*c].append([p,1])

    link[q+chg*c].append([p+chg*c,0])
    link[p+chg*c].append([q+chg*c,0])

    link[q+chg*c].append([q,1])
    link[q].append([q+chg*c,1])

def dks(g,start):
    INF=float('inf')
    visited = defaultdict(int)
    hq = []
    heappush(hq, (0,start))
    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if visited[i] != 0:
            continue
        visited[i] = 1
        cost[i] = shortest
        for j, t in g[i]:
            if visited[j] != 0:
                continue
            heappush(hq, (shortest + t, j))
    return cost
cost=dks(link,1)

ans=cost[n]
if ans == float("inf"):
    print((-1))
else:
    print((ans//2))

# Optimized solution
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
n,m = list(map(int, input().split()))
link = defaultdict(list)
chg=10**8
for _ in range(m):
    p,q,c=list(map(int, input().split()))
    link[p].append([p+chg*c,1])
    link[p+chg*c].append([p,1])

    link[q+chg*c].append([p+chg*c,0])
    link[p+chg*c].append([q+chg*c,0])

    link[q+chg*c].append([q,1])
    link[q].append([q+chg*c,1])

def dks(g,start):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        for j, t in g[i]:
            if j in visited:
                continue
            if j==n:
                return (shortest+t)//2
            heappush(hq, (shortest + t, j))
    return -1
ans=dks(link,1)
print(ans)
# Original solution
import sys
from collections import deque
N, M = list(map(int, input().split()))
Edge = [[] for _ in range(N+1)]
comp = set()
mod = 10**9+7
for _ in range(M):
    p, q, c = list(map(int, input().split()))
    Edge[p].append(mod*q+c)
    Edge[q].append(mod*p+c)
    comp.add(c)
dist = {mod: 0}
Q = deque()
Q.append(mod)
visited = set()
while Q:
    vn, cp = divmod(Q.pop(), mod)
    if mod*vn+cp in visited:
        continue
    if vn == N:
        break
    visited.add(mod*vn+cp)
    for t in Edge[vn]:
        vf, cf = divmod(t, mod)
        if mod*vf+cp in visited:
            continue
        if cp == cf:
            dist[mod*vf+cf] = dist.get(mod*vn+cp, 10**9)
            Q.append(mod*vf+cf)
        else:
            dist[mod*vf+cf] = min(dist.get(mod*vf+cf, 10**9), 1 + dist.get(mod*vn+cp, 10**9))
            Q.appendleft(mod*vf+cf)
L = [dist.get(N*mod+c, 10**9) for c in comp]
if not L or min(L) == 10**9:
    print((-1))
else:
    print((min(L)))


# Optimized solution
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
inf = 10**9+7
def dijkstra(N, s, Edge):    
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dn + df < dist[vf]:
                dist[vf] = dn + df
                hp(Q, (dn + df,vf))
    return dist

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


N, M = list(map(int, readline().split()))

Edge = []
VS = set(range(N))
geta = 20
Edge = [tuple(map(int, readline().split())) for _ in range(M)]
for a, b, c in Edge:
    a -= 1
    b -= 1
    VS |= {(c<<geta) | a, (c<<geta) | b}
   
_, Cv = compress(list(VS))

Vnum = len(Cv)

nEdge = [[] for _ in range(Vnum)]

for a, b, c in Edge:
    a -= 1
    b -= 1
    ca = Cv[(c<<geta) | a]
    cb = Cv[(c<<geta) | b]
    nEdge[ca].append((0, cb))
    nEdge[cb].append((0, ca))
    nEdge[a].append((1, ca))
    nEdge[ca].append((0, a))
    nEdge[b].append((1, cb))
    nEdge[cb].append((0, b))

dist = dijkstra(Vnum, 0, nEdge)
if dist[N-1] >= inf:
    dist[N-1] = -1
print((dist[N-1]))
# Original solution
from heapq import heappush, heappop
from collections import defaultdict

N, M = list(map(int, input().split()))
INF = 10**18

edges = defaultdict(set)
C = set()
for _ in range(M):
    fr, to, c = list(map(int, input().split()))
    edges[(fr, c)].add((to, c, 0))
    edges[(to, c)].add((fr, c, 0))

    edges[(fr, c)].add((fr, -1, 0))
    edges[(to, c)].add((to, -1, 0))

    edges[(fr, -1)].add((fr, c, 1))
    edges[(to, -1)].add((to, c, 1))
    C.add(c)

minDist = defaultdict(lambda: INF)
minDist[(1, -1)] = 0
que = [(0, 1, -1)]

while que:
    dist, now, c = heappop(que)

    for to, c, d in edges[(now, c)]:
        if minDist[(to, c)] > dist + d:
            minDist[(to, c)] = dist + d
            heappush(que, (dist + d, to, c))

ans = INF
for c in C:
    ans = min(ans, minDist[(N, c)])
print((ans if ans < INF else -1))


# Optimized solution
from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.buffer.readline

N, M = list(map(int, input().split()))
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = list(map(int, input().split()))
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0, 0)]
while que:
    dist, f, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

for _ in range(2):
    que = [(minDist[i], 0, i) for i in range(N)]
    heapify(que)
    while que:
        dist, f, now = heappop(que)

        for to, c in edges[now]:
            d = dist
            if not c in minDistList[now]:
                d += 1
            if minDist[to] > d:
                minDist[to] = d
                minDistList[to] = set()
                heappush(que, (d, f + 1, to))
            if minDist[to] == d:
                minDistList[to].add(c)

ans = minDist[N - 1]
print((ans if ans < 10**18 else -1))
# Original solution
from collections import*
from heapq import*
inf=10**18
n,m,*t=list(map(int,open(0).read().split()))
e=defaultdict(list)
s=[]
l=[]
f=g=False
for a,b,c in zip(t[::3],t[1::3],t[2::3]):
  if b<a:a,b=b,a
  if a<2:f=True
  if b==n:g=True
  x,y=a+n*c,b+n*c
  if b==n:l.append(y)
  e[a].append((1,x))
  e[b].append((1,y))
  e[x].extend([(0,a),(0,y)])
  e[y].extend([(0,b),(0,x)])
  s.extend([a,b,x,y])
if not(f and g):
  print((-1))
  exit()
d={i:v for v,i in enumerate(sorted(set(s)))}
l=[d[i]for i in l]
n=len(d)
edge=tuple([]for _ in range(n))
for i in e:
  edge[d[i]].extend([(c,d[j])for c,j in e[i]])
d=[inf]*n
used=[True]*n
d[0]=0
used[0]=False
edgelist=[]
for e in edge[0]:
  heappush(edgelist,e)
while len(edgelist):
  minedge=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]]:
      heappush(edgelist,(e[0]+d[v],e[1]))
a=min(d[i]for i in l)
print(([a,-1][a==inf]))

# Optimized solution
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**18
  n,m,*t=list(map(int,open(0).read().split()))
  e=defaultdict(list)
  s=[]
  l=[]
  f=g=False
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    if a<2:f=True
    if b==n:g=True
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    e[a].append((1,x))
    e[b].append((1,y))
    e[x].append((0,a))
    e[x].append((0,y))
    e[y].append((0,b))
    e[y].append((0,x))
    s.extend([a,b,x,y])
  if not(f and g):
    print((-1))
    exit()
  d={i:v for v,i in enumerate(sorted(set(s)))}
  l=[d[i]for i in l]
  n=len(d)
  edge=[[]for _ in range(n)]
  for i in e:
    edge[d[i]]=[(c,d[j])for c,j in e[i]]
  edge=tuple(edge)
  d=[inf]*n
  used=[True]*n
  d[0]=0
  used[0]=False
  edgelist=[]
  for e in edge[0]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=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]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min(d[i]for i in l)
  print(([a,-1][a==inf]))
if __name__=='__main__':
  main()