#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()






int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	int n, m;
	cin >> t >> n >> m;
	vector<vector<pair<int, int>>> edge(n, vector<pair<int, int>>());
	rep(_, m) {
		int u, v, w;
		cin >> u >> v >> w;
		u--; v--;
		edge[u].emplace_back(v, w);
		if (t == 0)edge[v].emplace_back(u, w);
	}
	rep(i, n) {
		sort(all(edge[i]));
	}

	long long ans = 1LL << 60;
	rep(i, n) {
		vector<long long> d(n, 1LL << 60);
		d[i] = 0;
		priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
		pq.emplace(0, i);

		while (!pq.empty()) {
			auto pa = pq.top();
			pq.pop();
			if (d[pa.second] < pa.first)continue;

			for (auto e : edge[pa.second]) {
				int v = e.first;
				int w = e.second;
				if (pa.first + w < d[v]) {
					d[v] = pa.first + w;
					pq.emplace(d[v], v);
				}
			}
		}
		rep(j, n) {
			for (auto e: edge[j]) {
				if (e.first == i && d[j] != e.second) {
					ans = min(ans, d[j] + e.second);
				}
			}
		}
	}

	if (ans == (1LL << 60))ans = -1;
	cout << ans << endl;


	return 0;
}