#include <bits/stdc++.h>

using namespace std;

void fast_io() {
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
}

int main() {
	fast_io();
	int t;
	cin >> t;
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, long long>>> g(n);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		g[u].push_back({v, w});
		if (t == 0) {
			g[v].push_back({u, w});
		}
	}
	long long ans = 1e18;
	for (int u0 = 0; u0 < n; u0++) {
		for (auto [v0, w0] : g[u0]) {
			vector<long long> dist(n, 1e18);
			dist[v0] = 0;
			using pli = pair<long long, int>;
			priority_queue<pli, vector<pli>, greater<pli>> pq;
			pq.push({0, v0});
			while (!pq.empty()) {
				auto [d, u] = pq.top();
				pq.pop();
				if (d > dist[u]) {
					continue;
				}
				for (auto [v, w] : g[u]) {
					if (u == u0 && v == v0) {
						continue;
					}
					if (t == 0 && u == v0 && v == u0) {
						continue;
					}
					if (dist[v] > dist[u] + w) {
						dist[v] = dist[u] + w;
						pq.push({dist[v], v});
					}
				}
			}
			ans = min(ans, dist[u0] + w0);
		}
	}
	if (ans >= 1e17) {
		ans = -1;
	}
	cout << ans << endl;
}