#include using namespace std; using weight = int64_t; using edge = pair; using vertice = vector; using graph = vector; using cost = tuple; int main() { constexpr int64_t inf = 1e18; int t, n, m; cin >> t >> n >> m; graph to(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--; v--; to.at(u).emplace_back(v, w); if (t == 0) { to.at(v).emplace_back(u, w); } } int64_t ans = inf; for (int i = 0; i < n; i++) { vector d(n, inf); priority_queue, greater> q; q.emplace(0, i, -1); while (not q.empty()) { auto [dist, v, from] = q.top(); q.pop(); if (v == i and dist > 0) { ans = min(ans, dist); break; } if (d.at(v) <= dist) continue; if (v != i) { d.at(v) = dist; } for (auto next : to.at(v)) { auto [next_v, next_w] = next; if (next_v == from) continue; int64_t next_dist = dist + next_w; if (d.at(next_v) <= next_dist) continue; q.emplace(next_dist, next_v, v); } } } if (ans == inf) { cout << -1 << endl; } else { cout << ans << endl; } }