import sys
import heapq
 
v,e = map(int, sys.stdin.readline().split())
times = [[] for _ in range(v + 1)]
all_v = []
 
for _ in range(e) :
  start, end, cost = map(int, sys.stdin.readline().split())
  times[start].append([cost, end])
  if start is not all_v :
    all_v.append(start)
 
def dijkstra(graph, start, all_v) :
  costs = {}
  pq = []
  heapq.heappush(pq, [0, start])
  while pq :
    cur_cost, cur_v = heapq.heappop(pq)
    if cur_v not in costs :
      costs[cur_v] = cur_cost
      for cost, next_v in graph[cur_v] :
        next_cost = cur_cost + cost
        heapq.heappush(pq, [next_cost, next_v])
 
  cost_keys = costs.keys()
  for v in all_v :
    if v not in cost_keys :
      return -1
 
  return max(cost_keys)
 
min_value = 1000000
for start_v in all_v :
  result = dijkstra(times, start_v, all_v)
  if result == -1 :
    continue
  else :
    min_value = min(result, min_value)
 
print(min_value)

import heapq
import sys
 
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
 
n, m = map(int, input().split())  # 노드 수, 간선 수
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)  # 노드의 방문 정보 초기화
 
# 무방향 그래프 생성
for i in range(m):  # 간성 정보 입력 받기
  start, end, weight = map(int, input().split())
  graph[start].append([weight, start, end])
  graph[end].append([weight, end, start])
 
# 프림 알고리즘
def prim(graph, start_node):
  visited[start_node] = 1  # 방문 갱신
  pq = graph[start_node]  # 인접 간선 추출
  heapq.heapify(pq)  # 우선순위 큐 생성
  total_cost = 0  # 전체 가중치
 
  while pq:
    weight, start, end = heapq.heappop(pq)  # 가중치가 가장 적은 간선 추출
    if visited[end] == 0:  # end가 방문하지 않았다면
      visited[end] = 1  # end 방문 갱신
      total_cost += weight  # 전체 가중치 갱신
 
      for edge in graph[end]:  # end가 start로 감
        if visited[edge[2]] == 0:  # edge[2]는 다음번 방문할 end
          heapq.heappush(pq, edge)
 
  return total_cost
 
print(prim(graph, 1))