prim, dijkstra

def prim(s, V):
  result = 0
  mst = [0] * (V + 1)
  mst[s] = 1

  for _ in range(V):
    u = 0
    minV = 1000000000
    for i in range(V + 1):
      if mst[i] == 1:
        for j in range(V + 1):
          if mst[j] == 0 and 0 < adj[i][j] < minV:  # 0이 아닌 것 중에(인접한 것 중에) 최솟값을 찾는다
            u = j
            minV = adj[i][j]
    mst[u] = 1
    result += minV
  return result

V, E = map(int, input().split())
adj = [[0] * (V + 1) for _ in range(V + 1)]
for _ in range(E):
  u, v, w = map(int, input().split())
  adj[u][v] = w
  adj[v][u] = w
ans = prim(0, V)
print(ans)

def dijkstra(s, V):
  U = [0] * (V + 1)
  U[s] = 1

  for i in range(V + 1):
    D[i] = adj[s][i]
  
  for _ in range(V):
    w = 0
    minV = INF
    for i in range(V + 1):
      if U[i] == 0 and minV > D[i]:  # 나머지 중 최솟값
        w = i
        minV = D[i]
    U[w] = 1
    for v in range(V + 1):
      if 0 < adj[w][v] < INF:  # 대상과 인접해 있으면(0이면 자기 자신, INF면 인접해 있지 않음)
        D[v] = min(D[v], D[w] + adj[w][v])

INF = 10000000
V, E = map(int, input().split())
adj = [[INF] * (V + 1) for _ in range(V + 1)]
for i in range(V + 1):
  adj[i][i] = 0
for _ in range(E):
  u, v, w = map(int, input().split())
  adj[u][v] = w
D = [0] * (V + 1)
dijkstra(0, V)
print(D)