Submission #1679075

---

Source Code Expand

n,m = map(int,input().split())
st = [1<<30]*(n+1)
wf = [[1<<30]*(n+1) for i in range(n+1)]
 
for _ in range(m):
    u,v,l = map(int,input().split())
    if u==1:
        st[v] = l
    else:
        wf[u][v] = wf[v][u] = l
for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            if wf[i][j] > wf[i][k] + wf[k][j]:
                wf[i][j] = wf[i][k] + wf[k][j]
 
ret = 1 << 30
for i in range(n+1):
    for j in range(n+1):
        if i==j: continue
        ret = min(st[i]+wf[i][j]+st[j],ret)
 
print(ret if ret < 10**6 else -1)

Submission Info

Judge Result