#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair; using pl = std::pair; using namespace std; template std::ostream &operator << (std::ostream &dest, const std::pair &p) { dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator << (std::ostream &dest, const std::tuple &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t); return dest; } template std::ostream &operator << (std::ostream &dest, const std::tuple &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t); return dest; } template std::ostream &operator << (std::ostream &dest, const std::tuple &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t); return dest; } template std::ostream &operator << (std::ostream &dest, const std::vector> &v) { int sz = v.size(); if (!sz) return dest; for (int i = 0; i < sz; i++) { int m = v[i].size(); for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' '); } return dest; } template std::ostream &operator << (std::ostream &dest, const std::vector &v) { int sz = v.size(); if (!sz) return dest; for (int i = 0; i < sz - 1; i++) dest << v[i] << ' '; dest << v[sz - 1]; return dest; } template std::ostream &operator << (std::ostream &dest, const std::array &v) { if (!sz) return dest; for (int i = 0; i < sz - 1; i++) dest << v[i] << ' '; dest << v[sz - 1]; return dest; } template std::ostream &operator << (std::ostream &dest, const std::set &v) { for (auto itr = v.begin(); itr != v.end();) { dest << *itr; itr++; if (itr != v.end()) dest << ' '; } return dest; } template std::ostream &operator << (std::ostream &dest, const std::map &v) { for (auto itr = v.begin(); itr != v.end(); ) { dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if (itr != v.end()) dest << '\n'; } return dest; } template std::vector make_vec(size_t sz, T val) { return std::vector(sz, val); } template auto make_vec(size_t sz, Tail ...tail) { return std::vector(tail...))>(sz, make_vec(tail...)); } template std::vector read_vec(size_t sz) { std::vector v(sz); for (int i = 0; i < (int)sz; i++) std::cin >> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail) { auto v = std::vector(tail...))>(sz); for (int i = 0; i < (int)sz; i++) v[i] = read_vec(tail...); return v; } template auto make_array(T x) { std::array res; res.fill(x); return res; } template auto make_array(T x) { std::array(x)), size> res; res.fill(make_array(x)); return res; } // x / y以上の最小の整数 ll ceil_div(ll x, ll y) { assert(y > 0); return (x + (x > 0 ? y - 1 : 0)) / y; } // x / y以下の最大の整数 ll floor_div(ll x, ll y) { assert(y > 0); return (x + (x > 0 ? 0 : -y + 1)) / y; } void io_init() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } template struct edge_base { using W = _W; int t; edge_base() {} edge_base(int _t) : t(_t) {} virtual int from() const { assert(false); } int to() const { return t; } virtual W weight() const { assert(false); } virtual int id() const { assert(false); } operator int() const { return t; } }; struct simple_edge : edge_base { simple_edge() {} simple_edge(int _t) : edge_base(_t) {} int weight() const override { return 1; } int id() const override { return -1; } }; struct labeled_edge : edge_base { int _s, _id; labeled_edge() {} labeled_edge(int _s, int _t, int _id) : edge_base(_t), _s(_s), _id(_id) {} int weight() const override { return 1; } int from() const override { return _s; } int id() const override { return _id; } }; template struct weighted_edge : edge_base<_W> { using W = _W; W w; weighted_edge() {} weighted_edge(int _t, _W _w) : edge_base<_W>(_t), w(_w) {} W weight() const override { return w; } int id() const override { return -1; } }; template struct weighted_labeled_edge : edge_base<_W> { using W = _W; W w; int _s, _id; weighted_labeled_edge() : _id(-1) {} weighted_labeled_edge(int _s, int _t, _W _w, int _id) : edge_base<_W>(_t), w(_w), _s(_s), _id(_id) {} int from() const override { return _s; } W weight() const override { return w; } int id() const override { return _id; } }; template struct csr { std::vector start; std::vector elist; csr() {} explicit csr(int n, const std::vector>& edges) : start(n + 1), elist(edges.size()) { for (auto e : edges) { start[e.first + 1]++; } for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; } auto counter = start; for (auto e : edges) { elist[counter[e.first]++] = e.second; } } ~csr() {} int N() const { return start.size() - 1; } int deg(int i) const { return start[i + 1] - start[i]; } int begin(int i) const { return start[i]; } int end(int i) const { return start[i + 1]; } E& operator [] (int i) { return elist[i]; } }; // 全体の最小コスト閉路 // 重みあり O(V(V + E)logV) template struct cycle_detection_mincost { using W = typename edge::W; static constexpr W inf = std::numeric_limits::max() / 2; private: csr g; std::pair, std::vector> bfs_tree(int s, W curw = inf) { int N = g.N(); std::vector dist(N, inf); std::vector par(N); std::queue q; q.push(s); dist[s] = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (int i = g.begin(v); i < g.end(v); i++) { int to = g[i]; if (dist[v] + 1 < dist[to] && dist[v] + 1 < curw) { dist[to] = dist[v] + 1; par[to] = g[i]; q.push(to); } } } return {dist, par}; } std::pair, std::vector> dijkstra_tree(int s, W curw = inf) { int N = g.N(); std::vector dist(N, inf); std::vector par(N); using P = std::pair; std::priority_queue, std::greater

> q; q.push({0, s}); dist[s] = 0; while (!q.empty()) { auto [d, v] = q.top(); q.pop(); if (dist[v] != d) continue; for (int i = g.begin(v); i < g.end(v); i++) { int to = g[i]; W nd = dist[v] + g[i].weight(); if (nd < dist[to] && nd < curw) { dist[to] = nd; par[to] = g[i]; q.push({nd, to}); } } } return {dist, par}; } public: cycle_detection_mincost(const csr &_g) : g(_g) {} // vを含む最小閉路 // 無向グラフの場合のみ辺のs-tが逆になっている場合があるがidの順序は正しい // 重みあり O((V + E)logV) // 重みなし O(V + E) std::pair> find(int v, bool directed, bool weighted, bool accept_self_loop) { int N = g.N(); W w = inf; int eid = -1; if (accept_self_loop) { for (int j = g.begin(v); j < g.end(v); j++) { if (g[j].to() == v && w < g[j].weight()) { w = g[j].weight(); eid = j; } } } std::vector dist; std::vector par; std::vector semi_root; if (weighted) { std::tie(dist, par) = dijkstra_tree(v); } else { std::tie(dist, par) = bfs_tree(v); } if (directed) { for (int i = 0; i < N; i++) { if (i == v || dist[i] >= w) continue; for (int j = g.begin(i); j < g.end(i); j++) { if (g[j].to() == v && dist[i] + g[j].weight() < w) { w = dist[i] + g[j].weight(); eid = j; } } } } else { semi_root.resize(N, -1); auto dfs = [&](auto &&dfs, int u, int p, int sr) -> void { semi_root[u] = sr; for (int i = g.begin(u); i < g.end(u); i++) { int to = g[i]; if (to == v || to == p || to == u || dist[to] >= w) continue; if (par[to].id() == g[i].id()) { dfs(dfs, to, u, sr); } } }; for (int i = 0; i < N; i++) { if (i == v || dist[i] >= w) continue; if (par[i].from() == v) dfs(dfs, i, v, i); } for (int i = 0; i < N; i++) { if (i == v || dist[i] >= w) continue; for (int j = g.begin(i); j < g.end(i); j++) { int to = g[j]; if (g[j].id() == par[i].id()) continue; if (semi_root[i] == semi_root[to]) continue; if (dist[i] + dist[to] + g[j].weight() < w) { w = dist[i] + dist[to] + g[j].weight(); eid = j; } } } } if (w == inf) return {inf, {}}; std::vector res; res.push_back(g[eid]); int u = g[eid].from(); while (u != v) { res.push_back(par[u]); u = par[u].from(); } std::reverse(res.begin(), res.end()); if (!directed) { u = g[eid].to(); while (u != v) { res.push_back(par[u]); u = par[u].from(); } } return {w, res}; } // 最小閉路 // 無向グラフの場合のみ辺のs-tが逆になっている場合があるがidの順序は正しい // 重みあり O((V + E)logV) // 重みなし O(V + E) std::pair> find(bool directed, bool weighted, bool accept_self_loop) { int N = g.N(); W w = inf; int r = -1, eid = -1; if (accept_self_loop) { for (int v = 0; v < N; v++) { for (int j = g.begin(v); j < g.end(v); j++) { if (g[j].to() == v && w < g[j].weight()) { w = g[j].weight(); r = v; eid = j; } } } } std::vector dist; std::vector par; std::vector semi_root(N, -1); std::vector ord(N); std::iota(ord.begin(), ord.end(), 0); std::random_device seed_gen; std::mt19937 engine(seed_gen()); std::shuffle(ord.begin(), ord.end(), engine); for (int v : ord) { if (weighted) { std::tie(dist, par) = dijkstra_tree(v, w); } else { std::tie(dist, par) = bfs_tree(v, w); } if (directed) { for (int i = 0; i < N; i++) { if (i == v || dist[i] >= w) continue; for (int j = g.begin(i); j < g.end(i); j++) { if (g[j].to() == v && dist[i] + g[j].weight() < w) { w = dist[i] + g[j].weight(); eid = j; r = v; } } } } else { std::fill(semi_root.begin(), semi_root.end(), -1); auto dfs = [&](auto &&dfs, int u, int p, int sr) -> void { semi_root[u] = sr; for (int i = g.begin(u); i < g.end(u); i++) { int to = g[i]; if (to == v || to == p || to == u || dist[to] >= w) continue; if (par[to].id() == g[i].id()) { dfs(dfs, to, u, sr); } } }; for (int i = 0; i < N; i++) { if (i == v || dist[i] >= w) continue; if (par[i].from() == v) dfs(dfs, i, v, i); } for (int i = 0; i < N; i++) { if (i == v || dist[i] >= w) continue; for (int j = g.begin(i); j < g.end(i); j++) { int to = g[j]; if (g[j].id() == par[i].id()) continue; if (semi_root[i] == semi_root[to]) continue; if (dist[i] + dist[to] + g[j].weight() < w) { w = dist[i] + dist[to] + g[j].weight(); r = v; eid = j; } } } } } if (w == inf) return {inf, {}}; if (weighted) { std::tie(dist, par) = dijkstra_tree(r); } else { std::tie(dist, par) = bfs_tree(r); } std::vector res; res.push_back(g[eid]); int u = g[eid].from(); while (u != r) { res.push_back(par[u]); u = par[u].from(); } std::reverse(res.begin(), res.end()); if (!directed) { u = g[eid].to(); while (u != r) { res.push_back(par[u]); u = par[u].from(); } } return {w, res}; } }; int main() { io_init(); int T; std::cin >> T; int N, M; std::cin >> N >> M; using edge = weighted_labeled_edge; std::vector> E; for (int i = 0; i < M; i++) { int a, b, c; std::cin >> a >> b >> c; a--, b--; E.push_back({a, {a, b, c, i}}); if (T == 0) { E.push_back({b, {b, a, c, i}}); } } cycle_detection_mincost G(csr(N, E)); long long w = G.find(T, true, true).first; std::cout << (w == G.inf ? -1 : w) << '\n'; }