Dijkstra，思维（Python）

思路：两次dijkstra求和。题目强调了是单向边，并且是单源最短路径问题，所以说很容易能够想到用一次dijkstra，求得邮局到其他点的最短路径。但是题目还说了，每次送完信还要回到邮局，并且由于是单向边，所以说就不能再走第一次dijkstra的路，回到邮局就是我们要算其他位置到邮局的最短路径。

这其实是一个多到一的问题，我们只需要额外建一个反向图，这样问题就能转化成标准的一到多dijkstra问题，然后就和第一次dijkstra的代码是一样的。所以说，我们就可以把dijkstra写成函数封装起来，然后分别去处理原图和反图，最终相加得到答案即可

代码：

import sys
from collections import deque
from heapq import heappop, heappush

input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n, m = MII()
    g = [[] for _ in range(n + 1)]
    flip_g = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, w = LII()
        g[u].append((v, w))
        flip_g[v].append((u, w))

    def dijkstra(g):
        dis = [inf] * (n + 1)
        dis[1] = 0
        h = [(0, 1)]
        while h:
            d, x = heappop(h)
            if d > dis[x]:
                continue
            for y, w in g[x]:
                new_dis = d + w
                if new_dis < dis[y]:
                    dis[y] = new_dis
                    heappush(h, (new_dis, y))
        return sum(dis[1:])

    print(dijkstra(g) + dijkstra(flip_g))

t = 1
# t = II()
for _ in range(t):
    solve()