import java.util.*; public class Main { static boolean isArrow; static boolean[][] used; static long min = Long.MAX_VALUE; static ArrayList> graph = new ArrayList<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); isArrow = (sc.nextInt() == 1); int n = sc.nextInt(); int m = sc.nextInt(); for (int i = 0; i < n; i++) { graph.add(new HashMap<>()); } for (int i = 0; i < m; i++) { int a = sc.nextInt() - 1; int b = sc.nextInt() - 1; int c = sc.nextInt(); graph.get(a).put(b, c); if (!isArrow) { graph.get(b).put(a, c); } } used = new boolean[n][n]; long[] costs = new long[n]; for (int i = 0; i < n; i++) { Arrays.fill(costs, 0); next(i, i, 1, costs); } if (min == Long.MAX_VALUE) { System.out.println(-1); } else { System.out.println(min); } } static void next(int idx, int from, long x, long[] costs) { if (costs[idx] != 0) { min = Math.min(min, x - costs[idx]); return; } if (used[from][idx]) { return; } used[from][idx] = true; costs[idx] = x; for (int y : graph.get(idx).keySet()) { if (!isArrow && y == from) { continue; } next(y, idx, x + graph.get(idx).get(y), costs); } costs[idx] = 0; } }