#!/usr/bin/env python3 import sys import heapq input = sys.stdin.readline inf = 1e15 def solve_undirected_graph(): N,M = map(int,input().split()) edges = [[] for i in range(N)] for i in range(M): u,v,w = map(int,input().split()) u-=1 v-=1 edges[u].append((v,w)) edges[v].append((u,w)) ans = inf for root in range(N): dist = [inf for i in range(N)] label = [-1 for i in range(N)] q = [(0,root)] dist[root] = 0 label[root] = root while len(q) > 0: cost,from_node = heapq.heappop(q) if cost > dist[from_node]: continue for to_node,w in edges[from_node]: if dist[to_node] > cost + w: dist[to_node] = cost + w if from_node == root: label[to_node] = to_node else : label[to_node] = label[from_node] heapq.heappush(q,(cost+w,to_node)) for from_node in range(N): for to_node,w in edges[from_node]: if from_node == root or to_node == root: continue if label[from_node] == label[to_node]: continue if ans > dist[from_node] + dist[to_node] + w: ans = dist[from_node] + dist[to_node] + w return ans def solve_directed_graph(): N,M = map(int,input().split()) edges = [[] for i in range(N)] for i in range(M): u,v,w = map(int,input().split()) u-=1 v-=1 edges[u].append((v,w)) ans = inf for root in range(N): dist = [inf for i in range(N)] q = [(0,root)] dist[root] = 0 while len(q) > 0: cost,from_node = heapq.heappop(q) if cost > dist[from_node]: continue for to_node,w in edges[from_node]: if dist[to_node] > cost + w: dist[to_node] = cost + w heapq.heappush(q,(cost+w,to_node)) if to_node == root and ans > dist[from_node] + w: ans = dist[from_node] + w return ans def main(): T = int(input()) ans = inf if T == 0: ans = solve_undirected_graph() else: ans = solve_directed_graph() if ans == inf: ans = -1 print(ans) main()