import heapq
def dijkstra(graph, s, t):
visited = [False for _ in range(len(graph))]
costs = [float('inf') for _ in range(len(graph))]
paths = [[] for _ in range(len(graph))]
priority_queue = []
heapq.heappush(priority_queue, (0, s, [s]))
costs[s - 1] = 0
paths[s - 1] = [s]
while priority_queue:
current_cost, current_node, current_path = heapq.heappop(priority_queue)
if current_cost > costs[current_node - 1]:
continue
visited[current_node - 1] = True
for neighbour in graph[current_node]:
cost = current_cost + neighbour[1]
path = current_path + [neighbour[0]]
if cost < costs[neighbour[0] - 1]:
costs[neighbour[0] - 1] = cost
paths[neighbour[0] - 1].append(path)
heapq.heappush(priority_queue, (cost, neighbour[0], path))
elif cost == costs[neighbour[0] - 1]:
paths[neighbour[0] - 1].append(path)
heapq.heappush(priority_queue, (cost, neighbour[0], path))
return costs[t - 1], paths[t - 1]
def commuter_pass(n, m, s, t, u, v, edges):
graph = {}
for i in range(1, n+1):
graph.update({i : []})
for a, b, c in edges:
graph[a].append([b, c])
graph[b].append([a, c])
st_cost, st_paths = dijkstra(graph, s, t)
min_cost = float('inf')
for path in st_paths:
min_su = min_sv = float("inf")
for node in path:
su_cost, su_paths = dijkstra(graph, node, u)
min_su = min(su_cost, min_su)
sv_cost, sv_paths = dijkstra(graph, node, v)
min_sv = min(sv_cost, min_sv)
min_cost = min(min_cost, min_su + min_sv)
return min_cost
n, m = map(int, input().split())
s, t = map(int, input().split())
u, v = map(int, input().split())
edges = []
for _ in range(m):
edge = list(map(int, input().split()))
edges.append(edge)
# print(n, m)
# print(s, t)
# print(u, v)
# print(edges)
result = commuter_pass(n, m, s, t, u, v, edges)
print(result)
