#line 2 ".lib/template.hpp"
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#define all(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>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<int, int>;
using pl = std::pair<ll, ll>;
template<typename T>
using vec = std::vector<T>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) 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<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}

void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}
#line 2 ".lib/graph/edge.hpp"

template<typename edge_weight>
struct edge_base{
  using weight = edge_weight;
  int to();
  int from();
  int id();
  weight wei();
  static weight z();
  edge_base<weight> reverse();
};

template<typename edge_weight>
struct simple_edge: edge_base<edge_weight>{
  using weight = edge_weight;
  int s, t;
  simple_edge(): s(-1), t(-1){}
  simple_edge(int a, int b): s(a), t(b){}
  int to(){return t;}
  int from(){return s;}
  int id(){return -1;}
  weight wei(){return 1;}
  static weight z(){return 0;}
  simple_edge<weight> reverse(){return simple_edge<weight>{t, s};}
};

template<typename edge_weight>
struct weighted_edge: edge_base<edge_weight>{
  using weight = edge_weight;
  int s, t;
  weight w;
  weighted_edge(): s(-1), t(-1), w(0){}
  weighted_edge(int a, int b, weight c): s(a), t(b), w(c){}
  int to(){return t;}
  int from(){return s;}
  int id(){return -1;}
  weight wei(){return w;}
  static weight z(){return 0;}
  weighted_edge<weight> reverse(){return weighted_edge<weight>{t, s, w};}
};

template<typename edge_weight>
struct labeled_edge: edge_base<edge_weight>{
  using weight = edge_weight;
  int s, t, i;
  labeled_edge(): s(-1), t(-1), i(-1){}
  labeled_edge(int a, int b, int i): s(a), t(b), i(i){}
  int to(){return t;}
  int from(){return s;}
  int id(){return i;}
  weight wei(){return 1;}
  static weight z(){return 0;}
  labeled_edge<weight> reverse(){return labeled_edge<weight>{t, s, i};}
};

template<typename edge_weight>
struct weighted_labeled_edge: edge_base<edge_weight>{
  using weight = edge_weight;
  int s, t, i;
  weight w;
  weighted_labeled_edge(): s(-1), t(-1), i(-1), w(0){}
  weighted_labeled_edge(int a, int b, weight w, int i): s(a), t(b), w(w), i(i){}
  int to(){return t;}
  int from(){return s;}
  int id(){return i;}
  weight wei(){return w;}
  static weight z(){return 0;}
  weighted_labeled_edge<weight> reverse(){return weighted_labeled_edge<weight>{t, s, i};}
};
#line 3 ".lib/graph/tree_algorithm.hpp"

// !
template<typename edge>
void tree_diameter_dfs(int cur, int par, typename edge::weight d, typename edge::weight &dmax, int &vmax, const vec<vec<edge>> &g){
  if(d > dmax) dmax = d, vmax = cur;
  for(edge &e : g[cur]){
    if(e.to() == par) continue;
    tree_diameter_dfs(e.to(), cur, d + e.wei(), dmax, vmax);
  }
}
// {直径, s, t}
template<typename edge>
std::tuple<typename edge::weight, int, int> tree_diameter(const vec<vec<edge>> &g){
  int s = 0, t = 0;
  typename edge::weight d = edge::z();
  tree_diameter_dfs(s, -1, 0, d, t, g);
  s = t, t = 0, d = edge::z();
  tree_diameter_dfs(s, -1, 0, d, t, g);
  return {d, s, t};
}
template<typename edge>
std::tuple<vec<vec<int>>, vec<int>, vec<int>, vec<int>> centroid_decomposition_build(const vec<vec<edge>> &g){
  int n = g.size();
  assert(n);
  vec<vec<int>> G(n);
  std::vector<int> size_i(n, 0), dep_i(n, std::numeric_limits<int>::max()), par_i(n, -1);

  auto add_edge = [&](int p, int c)->void{
    G[p].push_back(c);
    G[c].push_back(p);
    par_i[c] = p;
  };
  auto find_centroid = [&](auto &&find_centroid, int v, int p, const int N, const int8_t rank)->std::pair<int, int>{
    int sz = 1;
    for(edge &e: g[v]){
      if(e.t == p || dep_i[e.t] < rank) continue;
      auto [sz_c, cent_c] = find_centroid(find_centroid, e.t, v, N, rank);
      if(sz_c == -1) return {-1, cent_c};
      size_i[e.t] = sz_c, sz += sz_c;
    }
    //サイズが半分以上になったとき
    if(sz * 2 >= N){
      size_i[v] = N;
      dep_i[v] = rank;
      for(edge &e: g[v]){
        if(e.t == p || dep_i[e.t] < rank) continue;
        auto [sz_c, cent_c] = find_centroid(find_centroid, e.t, -1, size_i[e.t], rank + 1);
        assert(sz_c == -1);
        add_edge(v, cent_c);
      }
      if(p != -1){
        auto [sz_c, cent_c] = find_centroid(find_centroid, p, -1, N - sz, rank + 1);
        assert(sz_c == -1);
        add_edge(v, cent_c);
      }
      return {-1, v};// 重心を発見
    }
    return {sz, -1};
  };
  find_centroid(find_centroid, 0, -1, n, 0);
  return {G, size_i, dep_i, par_i};
}
template<typename edge>
struct hld{
  vec<int> subsize, depth, parent, in, out, head, rev;
  hld(vec<vec<edge>> &g, int root){
    build(g, root);
  }
  void dfs_sz(int cur, int par, int dep, vec<vec<edge>> &g){
    depth[cur] = dep;
    parent[cur] = par;
    subsize[cur] = 1;
    if(g[cur].size() && g[cur][0].to() == par) std::swap(g[cur][0], g[cur].back());
    for(int i = 0; i < g[cur].size(); i++){
      edge &e = g[cur][i];
      if(e.to() == par) continue;
      dfs_sz(e.to(), cur, dep + 1, g);
      subsize[cur] += subsize[e.to()];
      if(subsize[g[cur][0].to()] < subsize[e.to()]) std::swap(g[cur][0], e);
    }
  }
  void dfs_hld(int cur, int par, int &times, vec<vec<edge>> &g){
    in[cur] = times++;
    rev[in[cur]] = cur;
    for(edge &e : g[cur]){
      if(e.to() == par) continue;
      head[e.to()] = (g[cur][0].to() == e.to() ? head[cur] : e.to());
      dfs_hld(e.to(), cur, times, g);
    }
    out[cur] = times;
  }
  void build(vec<vec<edge>> &g, int root){
    int n = g.size();
    subsize.resize(n), depth.resize(n), parent.resize(n);
    in.resize(n), out.resize(n), head.resize(n), rev.resize(n);
    dfs_sz(root, -1, 0, g);
    int t = 0;
    dfs_hld(root, -1, t, g);
  }
  int la(int v, int k){
    if(depth[v] < k) return -1;
    while(true){
      int u = head[v];
      if(in[v] - k >= in[u]) return rev[in[v] - k];
      k -= in[v] - in[u] + 1;
      v = parent[u];
    }
  }
  int lca(int u, int v){
    for(;; v = parent[head[v]]){
      if(in[u] > in[v]) std::swap(u, v);
      if(head[u] == head[v]) return u;
    }
  }
  bool is_ancestor(int u, int v){
    if(depth[u] > depth[v]) std::swap(u, v);
    return u == la(v, depth[v] - depth[u]);
  }
  int kth_vertex_on_path(int u, int v, int k){
    int l = lca(u, v), dlu = depth[u] - depth[l];
    if(dlu > k) return la(u, k);
    k = depth[v] - depth[l] - k + dlu;
    if(k < 0) return -1;
    return la(v, k);
  }
  // hldに基づいて頂点を[0, n), 辺を[1, n)に並び替えた時に, 任意のパスはO(log(n))個の区間になる

  // 頂点[0, n)の中でuの位置
  int index_vertex(int u){
    return in[u];
  }
  // 辺[1, n)の中でe{s, t}の位置, 辺が存在しない場合は-1
  int index_edge(int s, int t){
    if(in[s] > in[t]) std::swap(s, t);
    if(parent[t] != s) return -1;
    return in[s] + 1;
  }
  using path = vec<std::pair<int, int>>;
  // 順序を気にせずO(log(n))個の区間を列挙
  path unordered_path(int u, int v, bool is_edge = false){
    path res;
    for(;; v = parent[head[v]]){
      if(in[u] > in[v]) std::swap(u, v);
      if(head[u] == head[v]) break;
      res.push_back({in[head[v]], in[v] + 1});
    }
    res.push_back({in[u] + is_edge, in[v] + 1});
    return res;
  }
  // {lca->uのパス, lca->vのパス}
  std::pair<path, path> ordered_path(int u, int v, bool is_edge = false){
    bool is_swaped = false;
    std::pair<path, path> res;
    path &a = res.first, &b = res.second;
    for(;; v = parent[head[v]]){
      if(in[u] > in[v]) std::swap(u, v), std::swap(a, b), is_swaped ^= 1;
      if(head[u] == head[v]) break;
      b.push_back({in[head[v]], in[v] + 1});
    }
    b.push_back({in[u] + is_edge, in[v] + 1});
    if(is_swaped) std::swap(a, b);
    std::reverse(a.begin(), a.end());
    std::reverse(b.begin(), b.end());
    return {a, b};
  }
};
// !
// 部分木のサイズ, 深さ, 親
template<typename edge>
std::tuple<vec<int>, vec<int>, vec<int>> simple_dfs(const vec<vec<edge>> &g, int root){
  int n = g.size();
  vec<int> sz(n, 1), de(n), pa(n);
  auto simple_dfs_f = [&](auto simple_dfs_f, int cur, int par, int dep)->void{
    pa[cur] = par;
    de[cur] = dep;
    for(edge &e : g[cur]){
      if(e.to() == par) continue;
      simple_dfs_f(simple_dfs_f, e.to(), cur, dep + 1);
      sz[cur] += sz[e.to()];
    }
  };
  simple_dfs_f(simple_dfs_f, root, -1, 0);
  return {sz, de, pa};
}

// !
// pre_order 頂点を初めて訪れた時刻を記録
// in_pre: 初めて訪れた時刻
// out_pre: in_pre以降に初めてvより上のノードが現れる時刻, 区間[in_pre, out_pre)は部分木
// rev_pre: in_preの順番に頂点を並び替えた状態
template<typename edge>
struct dfs_order{
  vec<int> subsize, depth, parent;
  vec<int> in_pre, out_pre, rev_pre;// 訪れた順番(サイズN)
  vec<int> in_path, out_path, rev_path;// 戻る辺も考慮する(サイズ2N-1)
  dfs_order(vec<vec<edge>> &g, int root){
    build(g, root);
  }
  void dfs_build_inner(int cur, int par, int dep, int &tpath, int &tpre, vec<vec<edge>> &g){
    depth[cur] = dep;
    parent[cur] = par;
    in_path[cur] = tpath;
    rev_path[tpath++] = cur;
    in_pre[cur] = out_path[cur] = tpre;
    rev_pre[tpre++] = cur;
    for(int i = 0; i < g[cur].size(); i++){
      int to = g[cur][i].to();
      if(to == par) continue;
      dfs_build_inner(to, cur, dep + 1, tpath, tpre, g);
      subsize[cur] += subsize[to];
      out_path[cur] = tpath;
      rev_path[tpath++] = cur;
    }
    out_pre[cur] = tpre;
  }
  void build(vec<vec<edge>> &g, int root){
    int n = g.size();
    depth.resize(n), parent.resize(n), subsize.resize(n, 1);
    in_pre.resize(n), out_pre.resize(n), rev_pre.resize(n);
    in_path.resize(n), out_path.resize(n), rev_path.resize(2 * n - 1);
    int a = 0, b = 0;
    dfs_build_inner(root, -1, 0, a, b, g);
  }
  // vがuの部分木に含まれるか(u自身も部分木)
  bool is_subtree(int u, int v){
    return in_path[u] <= in_path[v] && out_path[v] <= out_path[u];
  }
  // u->vパス(最短経路)にwが含まれるか(端点も含む)
  // vがuの部分木 -> wがuの部分木 && vがwの部分木
  // それ以外 -> wがuかvのどちらかを部分木として含む
  bool is_contained_path(int u, int v, int w){
    if(in_path[u] > in_path[v]) std::swap(u, v);
    if(is_subtree(u, v)) return in_path[u] <= in_path[w] && is_subtree(w, v);
    return is_subtree(w, u) || is_subtree(w, v);
  }
  // [in_pre, out_pre)がuの部分木中に存在する頂点番号
  std::pair<int, int> subtree(int u){
    return {in_pre[u], out_pre[u]};
  }
  /*
  std::pair<int, int> path(){

  }
  */
};

// !
template<typename edge>
struct bfs_order{
  vec<int> parent;
  vec<int> in_bfs, rev_bfs, child_in;
  vec<vec<edge>> &g;
  bfs_order(vec<vec<edge>> &g, int root):g(g){
    build(root);
  }
  // 注: g[v][親]が末尾にswapされる
  void build(int root){
    int n = g.size();
    in_bfs.resize(n);
    rev_bfs.resize(n);
    child_in.resize(n, -1);
    parent.resize(n);
    std::queue<std::pair<int, int>> q;
    q.push({root, -1});
    int t = 0;
    while(!q.empty()){
      auto [v, p] = q.front();
      q.pop();
      parent[v] = p;
      if(child_in[p] == -1) child_in[p] = t;
      rev_bfs[t] = v;
      in_bfs[v] = t++;
      for(int i = 0; i < g[v].size(); i++){
        if(g[v][i].to() == p) std::swap(g[v][i], g[v].back());
        q.push({g[v][i].to(), v});
      }
    }
  }
  // vがuの何番目の子か(0-indexed), 親でない場合-1
  int child_index_find(int u, int v){
    if(parent[v] != u) return -1;
    return in_bfs[v] - child_in[u];
  }
  // e{u, v}を探す
  edge get_edge(int u, int v){
    return g[u][child_index_find(u, v)];
  }
  edge get_parent_edge(int u){
    /*
    // 辺が親->子片方向だと壊れる
    return g[u].back();
    */
    int p = parent[u];
    return g[p][child_index_find(p, u)];
  }
};

template<int (*lca)(int, int), int (*dfs_in)(int), int (*dep)(int)>
std::pair<vec<int>, vec<std::pair<int, int>>> lca_tree_build(vec<int> v){
  if(v.empty()) return {};
  std::sort(v.begin(), v.end(), [&](int a, int b){return dfs_in(a) < dfs_in(b);});
  v.erase(std::unique(v.begin(), v.end()), v.end());
  std::stack<int> st;
  vec<std::pair<int, int>> E;
  vec<int> V;
  st.push(v[0]);
  for(int i = 1; i < v.size(); i++){
    if(v[i] == v[i - 1]) continue;
    int l = lca(v[i], v[i - 1]);
    while(true){
      int c = st.top();
      st.pop();
      if(st.empty() || dep(st.top()) <= dep(l)){
        st.push(l);
        st.push(v[i]);
        if(dep(c) > dep(l)){
          E.push_back({l, c});
          V.push_back(c);
          V.push_back(l);
        }
        break;
      }
      int p = st.top();
      if(dep(c) > dep(p)){
        E.push_back({p, c});
        V.push_back(c), V.push_back(p);
      }
    }
  }
  while(st.size() >= 2){
    int c = st.top();
    st.pop();
    int p = st.top();
    if(c != p) E.push_back({p, c}), V.push_back(c), V.push_back(p);
  }
  if(!st.empty()) V.push_back(st.top());
  std::sort(V.begin(), V.end());
  V.erase(std::unique(V.begin(), V.end()), V.end());
  return {V, E};
}
#line 5 ".lib/graph/tree.hpp"

template<typename edge>
struct tree{
  using weight = typename edge::weight;
  template<typename T>
  using vec = std::vector<T>;
  using graph = vec<vec<edge>>;
  using simple_tree = tree<simple_edge<int>>;
public:
  graph g;
  int n, r;
  vec<int> subsize, depth, parent;
  hld<edge> *hld_p;
  dfs_order<edge> *dfs_p;
  bfs_order<edge> *bfs_p;
  tree(int n, int r = 0): g(n), n(n), r(r), hld_p(nullptr), dfs_p(nullptr), bfs_p(nullptr){}
  tree(graph &g, int r = 0): g(g), n(g.size()), r(r), hld_p(nullptr), dfs_p(nullptr), bfs_p(nullptr){}

  void add_edge(int a, edge e){
    assert(0 <= a && a < n);
    g[a].push_back(e);
  }
  void add_dual(int a, int b, edge e){
    assert(0 <= a && a < n);
    g[a].push_back(e);
    g[b].push_back(e.reverse());
  }
  void simple_dfs(){
    auto [s, d, p] = simple_dfs(g, r);
    subsize = s, depth = d, parent = p;
  }
  void hld_build(){
    hld_p = new hld<edge>(g, r);
    subsize = hld_p->subsize, depth = hld_p->depth, parent = hld_p->parent;
  }
  void dfs_build(){
    dfs_p = new dfs_order(g, r);
    subsize = dfs_p->subsize, depth = dfs_p->depth, parent = dfs_p->parent;
  }
  void bfs_build(){
    bfs_p = new bfs_order(g, r);
    parent = bfs_p->parent;
  }
  int lca(int u, int v){
    return hld_p->lca(u, v);
  }
  int la(int u, int k){
    return hld_p->la(u, k);
  }
  int dep(int v){
    return depth[v];
  }
  int par(int v){
    return parent[v];
  }
  int size(int v){
    return subsize[v];
  }
  std::pair<vec<int>, vec<std::pair<int, int>>> lca_tree(vec<int> v){
    static std::function<int(int, int)> dfs_in = [&](int v){return dfs_p->in_pre[v];};
    return lca_tree_build<lca, dfs_in, dep>(v);
  }
  // vがuの何番目の子か(0-indexed), 親でない場合-1
  int child_index_find(int u, int v){
    return bfs_p->child_index_find(u, v);
  }
  // s->tパスの辺
  vec<edge> get_path(int s, int t){
    int l = lca(s, t);
    vec<edge> L, R;
    while(s != l){
      L.push_back(g[s].back());
      s = parent[s];
    }
    while(t != l){
      int p = parent[l];
      R.push_back(g[p][child_index_find(p, l)]);
      l = p;
    }
    std::reverse(R.begin(), R.end());
    L.insert(L.end(), R.begin(), R.end());
    return L;
  }
  // vがuの部分木に含まれるか(u自身も部分木)
  bool is_subtree(int u, int v){
    return dfs_p->is_subtree(u, v);
  }
  // u->vパス(最短経路)にwが含まれるか(端点も含む)
  // vがuの部分木 -> wがuの部分木 && vがwの部分木
  // それ以外 -> wがuかvのどちらかを部分木として含む
  bool is_contained_path(int u, int v, int w){
    return dfs_p->is_contained_path(u, v, w);
  }
  simple_tree centroid_decomposition(){
    auto [G, root, size_i, par_i, dep_i] = centroid_decomposition_build<edge>(g);
    simple_tree res(G, root);
    res.subsize = size_i;
    res.parent = par_i;
    res.depth = dep_i;
    return res;
  }
  vec<edge> &operator [](int i){return g[i];}
};
using simple_tree = tree<simple_edge<int>>;
#line 5 ".lib/graph/graph_algorithm.hpp"

// i-bit目が1 -> 頂点iを使う
long long maximum_independent_set(const vec<long long> &g2, long long rem){
  int n = g2.size();
  if(rem == -1) rem = (1LL << n) - 1;
  long long ret = 0;
  int k = -1, m = -1;
  while(true){
    bool update = false;
    for(int i = 0; i < n; i++){
      if(!((rem >> i) & 1)) continue;
      int s = __builtin_popcountll(rem & g2[i]); //次数
      if(s > m) k = i, m = s;
      if(s <= 1){
        rem &= ~(g2[i] | (1LL << i));
        ret |= (1LL << i), update = true;
      }
    }
    if(!update) break;
    k = -1, m = -1;
  }
  if(rem > 0){
    rem &= ~(1LL << k);
    long long p = maximum_independent_set(g2, rem); //kを使わない
    long long q = maximum_independent_set(g2, rem & ~g2[k]); //kを使う
    if(__builtin_popcountll(p) > __builtin_popcountll(q)) ret |= p;
    else ret |= ((1LL << k) | q);
  }
  return ret;
}

// プリム法, 連結なら始点sは関係ない
template<typename edge>
vec<edge> undirected_mst(vec<vec<edge>> &g, int s = 0){
  int n = g.size();
  assert(s < n);
  static vec<bool> V(n, 0);
  vec<edge> res;
  using pde = pair<typename edge::weight, edge>;
  std::priority_queue<pde, vec<pde>, std::function<bool(pde, pde)>> que([](pde a, pde b){
    return a.first > b.first;
  });
  V[s] = true;
  for(edge &e : g[s]) que.push(pde{e.wei(), e});
  while(!que.empty()){
    auto [d, e] = que.top();
    que.pop();
    if(V[e.to()]) continue;
    V[e.to()] = true;
    res.push_back(e);
    for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});
  }
  for(edge &e : res) V[e.to()] = V[e.from()] = false;
  return res;
}
// !
// プリム法
template<typename edge>
vec<vec<edge>> undirected_mst_forest(vec<vec<edge>> &g){
  int n = g.size();
  static vec<bool> V(n, 0);
  vec<vec<edge>> res;
  using pde = pair<typename edge::weight, edge>;
  std::priority_queue<pde, vec<pde>, std::function<bool(pde, pde)>> que([](pde a, pde b){
    return a.first > b.first;
  });
  for(int i = 0; i < n; i++){
    if(V[i]) continue;
    V[i] = true;
    res.push_back(vec<edge>());
    for(edge &e : g[i]) que.push(pde{e.wei(), e});
    while(!que.empty()){
      auto [d, e] = que.top();
      que.pop();
      if(V[e.to()]) continue;
      V[e.to()] = true;
      res.push_back(e);
      for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});
    }
    for(edge &e : res.back()) V[e.to()] = V[e.from()] = false;
  }
  return res;
}

// !
// 終了時にinが0でない要素がある -> 閉路が存在する
template<typename edge>
vec<int> topological_sort(vec<vec<edge>> &g){
  int n = g.size();
  std::queue<int> que;
  vec<int> in(n, 0), res;
  for(int i = 0; i < n; i++) for(edge e : g[i]) in[e.to()]++;
  for(int i = 0; i < n; i++) if(!in[i]) que.push(i);
  while(!que.empty()){
    int p = que.front();
    que.pop();
    res.push_back(p);
    for(edge &e : g[p]){
      int to = e.to();
      if(!(--in[to])) que.push(to);
    }
  }
  return res;
}

template<typename edge>
pair<vec<int>, vec<vec<int>>> scc(vec<vec<edge>> &g){
  int n = g.size();
  vec<int> v(n), cmp(n, 0);
  vec<vec<int>> rg(n), V;
  auto scc_dfs = [&](auto &&scc_dfs, int cur, int &sz)->void{
    cmp[cur] = -1;
    for(edge &e : g[cur]){
      int to = e.to();
      rg[to].push_back(cur);
      if(cmp[to] == 0) scc_dfs(scc_dfs, to, sz);
    }
    v[sz++] = cur;
  };
  auto scc_rdfs = [&](auto &&scc_rdfs, int cur, const int k)->void{
    cmp[cur] = k;
    V[k].push_back(cur);
    for(int to : rg[cur]) if(cmp[to] == -1) scc_rdfs(scc_rdfs, to, k);
  };
  for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) scc_dfs(scc_dfs, i, j);
  for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){
    if(cmp[v[i]] == -1){
      V.push_back(vec<int>());
      scc_rdfs(scc_rdfs, v[i], j++);
    }
  }
  return {cmp, V};
}


template<typename edge>
pair<vec<int>, vec<vec<int>>> two_edge_connected(vec<vec<edge>> &g){
  int n = g.size();
  vec<int> v(n), cmp(n, 0);
  vec<vec<int>> V;
  vec<vec<bool>> edge_used(n);
  auto tec_dfs = [&](auto &&tec_dfs, int cur, int &sz)->void{
    cmp[cur] = -1;
    for(int i = 0; i < g[cur].size(); i++){
      int to = g[cur][i].to();
      if(cmp[to] == 0) edge_used[cur][i] = true, tec_dfs(tec_dfs, to, sz);
    }
    v[sz++] = cur;
  };
  auto tec_rdfs = [&](auto &&tec_rdfs, int cur, const int k)->void{
    cmp[cur] = k;
    V[k].push_back(cur);
    for(int i = 0; i < g[cur].size(); i++){
      int to = g[cur][i].to();
      if(cmp[to] == -1 && !edge_used[cur][i]) tec_rdfs(tec_rdfs, to, k);
    }
  };
  for(int i = 0; i < n; i++) edge_used[i].resize(g[i].size(), 0);
  for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) tec_dfs(tec_dfs, i, j);
  for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){
    if(cmp[v[i]] == -1){
      V.push_back(vec<int>());
      tec_rdfs(tec_rdfs, v[i], j++);
    }
  }
  return {cmp, V};
}

// 二重頂点連結成分分解
template<typename edge>
pair<vec<int>, vec<vec<int>>> bcc(vec<vec<edge>> &g){
  int n = g.size();
  vec<vec<int>> V;
  vec<int> child(n, 0), dep(n, -1), low(n);
  vec<bool> used(n, false), is_articulation(n, false);
  vec<edge> tmp_edge;

  auto bcc_dfs = [&](auto &&bcc_dfs, int cur, int par, int d)->void{
    if(par != -1) child[par]++;
    dep[cur] = low[cur] = d;
    for(edge &e : g[cur]){
      int to = e.to();
      if(to == par) continue;
      if(dep[to] < dep[cur]) tmp_edge.push_back(e);
      if(dep[e.to()] == -1){
        bcc_dfs(bcc_dfs, to, cur, d + 1);
        if(low[to] >= dep[cur]){
          is_articulation[cur] = true;
          V.push_back(vec<int>());
          bool is_ok = false;
          while(!tmp_edge.empty() && !is_ok){
            edge e = tmp_edge.back();
            tmp_edge.pop_back();
            if(e.from() == cur && e.to() == to) is_ok = true;
            if(!used[e.to()]) V.back().push_back(e.to()), used[e.to()] = true;
            if(!used[e.from()]) V.back().push_back(e.from()), used[e.from()] = true;
          }
          for(int v : V.back()) used[v] = false;
        }
        low[cur] = std::min(low[cur], low[to]);
      }else low[cur] = std::min(low[cur], dep[to]);
    }
  };
  for(int i = 0; i < n; i++){
    if(dep[i] != -1) continue;
    int vsz_pre = V.size();
    bcc_dfs(bcc_dfs, i, -1, 0);
    is_articulation[i] = (child[i] > 1);
    if(V.size() == vsz_pre) V.push_back(vec<int>{i});// 孤立点
  }
  return {child, V};
}

// !
// g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)
template<typename edge>
void cmp_edge_arrange(const vec<int> &cmp, vec<vec<edge>> &g){
  int n = g.size();
  for(int i = 0; i < n; i++){
    int m = g[i].size();
    int l = 0, r = m - 1;
    while(l < r){
      while(l < m && cmp[i] == cmp[g[i][l].to()]) l++;
      while(0 < r && cmp[i] == cmp[g[i][r].to()]) r--;
      if(l < r) std::swap(g[i][l], g[i][r]);
    }
  }
}

// !
// rを根とするbfs木, 重みを気にしない O(V + E)
template<typename edge>
tree<edge> bfs_tree(vec<vec<edge>> &g, int r){
  int n = g.size();
  std::queue<int> que;
  vec<bool> used(n, false);
  que.push(r);
  tree<edge> res(n, r);
  used[r] = true;
  while(!que.empty()){
    int v = que.front();
    que.pop();
    for(edge &e : g[v]){
      int to = e.to();
      if(used[to]) continue;
      used[to] = true;
      res.add_edge(v, e);
      que.push(to);
    }
  }
  return res;
}

// !
// rを根とするbfs木, 最短経路的 O((V + E)logV)
// {木, 重みのテーブル}
template<typename edge>
std::pair<tree<edge>, vec<typename edge::weight>> bfs_tree_shortest(vec<vec<edge>> &g, int r){
  int n = g.size();
  using weight = typename edge::weight;
  using pdv = std::pair<weight, int>;
  static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
  std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> que;
  vec<weight> dist(n, inf);
  dist[r] = edge::z();
  que.push({edge::z(), r});
  tree<edge> res(n, r);
  while(!que.empty()){
    auto [d, v] = que.top();
    que.pop();
    if(dist[v] < d) continue;
    for(edge &e : g[v]){
      int to = e.to();
      weight nxtd = d + e.wei();
      if(dist[to] > nxtd){
        dist[to] = nxtd;
        res.add_edge(v, e);
        que.push({nxtd, to});
      }
    }
  }
  return {res, dist};
}

// O((V + E)logV)
// 辺の重みが非負
template<typename edge>
struct dijkstra{
private:
  using weight = typename edge::weight;
  using dist_p = pair<weight, int>;
  vec<vec<edge>> &g;
public:
  dijkstra(vec<vec<edge>> &g): g(g){}
  static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
  static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
  vec<weight> dist;
  vec<edge> par;
  void build(int s){
    int n = g.size();
    if(dist.empty()){
      dist.resize(n, inf);
      par.resize(n, edge{});
    }else{
      std::fill(dist.begin(), dist.end(), inf);
      std::fill(par.begin(), par.end(), edge{});
    }
    std::priority_queue<dist_p, vec<dist_p>, std::greater<dist_p>> que;
    dist[s] = edge::z();
    que.push(dist_p(edge::z(), s));
    while(!que.empty()){
      auto [w, v] = que.top();
      que.pop();
      if(dist[v] < w) continue;
      for(edge &e: g[v]){
        weight d = dist[v] + e.wei();
        int to = e.to();
        if(dist[to] > d){
          dist[to] = d;
          par[to] = e;
          que.push(dist_p(d, to));
        }
      }
    }
  }
  vec<edge> get_path(int v){
    assert(!dist.empty());
    vec<edge> res;
    while(par[v].from() != -1) res.push_back(par[v]), v = par[v].from();
    std::reverse(res.begin(), res.end());
    return res;
  }
  weight operator [](int v){return dist[v];}
};

// O(VE)
// inf: 到達不可, minf: 負の閉路
template<typename edge>
struct bellman_ford{
private:
  using weight = typename edge::weight;
  using dist_p = pair<weight, int>;
  vec<vec<edge>> &g;
public:
  bellman_ford(vec<vec<edge>> &g): g(g){}
  static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
  static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
  vec<weight> dist;
  vec<edge> par;

  void build(int s){
    int n = g.size();
    if(dist.empty()){
      dist.resize(n, inf);
      par.resize(n);
    }else{
      std::fill(dist.begin(), dist.end(), inf);
      std::fill(par.begin(), par.end(), edge{});
    }
    dist[s] = edge::z();
    for(int lp = 0; ; lp++){
      bool update = false;
      for(int i = 0; i < n; i++){
        if(dist[i] == inf) continue;
        for(edge e : g[i]){
          weight &dto = dist[e.to()];
          if(dto == minf){
            if(dto != minf) update = true;
            dto = minf;
          }else if(dto == inf || dto > dist[i] + e.wei()){
            dto = (lp > n ? minf : dist[i] + e.wei());
            par[e.to()] = e;
            update = true;
          }
        }
      }
      if(!update) break;
    }
  }
  vec<edge> get_path(int v){
    assert(!dist.empty());
    vec<edge> res;
    while(par[v].from() != -1) res.push_back(par[v]), v = par[v].from();
    std::reverse(res.begin(), res.end());
    return res;
  }
  weight operator [](int v){return dist[v];}
};

// O(V^3)
template<typename edge>
struct warshall_floyd{
private:
  using weight = typename edge::weight;
  vec<vec<edge>> &g;
public:
  warshall_floyd(vec<vec<edge>> &g): g(g){}
  static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
  static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
  vec<vec<weight>> dist;
  void build(){
    int n = g.size();
    dist.resize(n, vec<weight>(n, inf));
    for(int i = 0; i < n; i++){
      dist[i][i] = 0;
      for(edge &e : g[i]){
        dist[i][e.to()] = std::min(dist[i][e.to()], e.wei());
      }
    }
    for(int k = 0; k < n; k++){
      for(int s = 0; s < n; s++){
        for(int t = 0; t < n; t++){
          dist[s][t] = std::min(dist[s][t], dist[s][k] + dist[k][t]);
        }
      }
    }
  }
  vec<weight>& operator [](int v){return dist[v];}
};
#line 5 ".lib/graph/graph.hpp"

/*
template<typename edge = int, typename dist = int, typename edge_type = simple_edge<edge, dist>>
struct dense_graph{

};
*/
template<typename edge>
struct general_graph{
  using weight = typename edge::weight;
  template<typename T>
  using vec = std::vector<T>;
  using graph = vec<vec<edge>>;
  int n;
  graph g;
  general_graph(int n): n(n), g(n){}

  void add_edge(int a, edge e){
    g[a].push_back(e);
  }

  // i-bit目が1 -> 頂点iを使う
  long long maximum_independent_set(){
    assert(n <= 62);
    vec<long long> g2(n, 0);
    for(int i = 0; i < n; i++) for(edge &e : g[i]) g2[i] |= (1LL << e.to());
    return maximum_independent_set(g2, -1);
  }

  // !
  vec<edge> undirected_mst_build(int s = 0){
    return undirected_mst<edge>(g, s);
  }
  // 終了時にinが0でない要素がある -> 閉路が存在する
  vec<int> topological_sort(){
    return topological_sort(g);
  }
  pair<vec<int>, vec<vec<int>>> scc(){
    return scc(g);
  }
  pair<vec<int>, vec<vec<int>>> two_edge_connected_build(){
    return two_edge_connected<edge>(g);
  }
  pair<vec<int>, vec<vec<int>>> bcc_build(){
    return bcc<edge>(g);
  }
  // g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)
  void cmp_edge_arrange(const vec<int> &cmp){
    cmp_edge_arrange(cmp, g);
  }
  // rを根とするbfs木, 重みを気にしない O(V + E)
  tree<edge> bfs_tree(int r){
    return bfs_tree(g, r);
  }
  // rを根とするbfs木, 最短経路的 O((V + E)logV)
  tree<edge> bfs_tree_shortest(int r){
    return bfs_tree_shortest(g, r);
  }
  dijkstra<edge> dijkstra_build(){
    return dijkstra<edge>(g);
  }
  bellman_ford<edge> bellman_ford_build(){
    return bellman_ford<edge>(g);
  }
  warshall_floyd<edge> warshall_floyd_build(){
    return warshall_floyd<edge>(g);
  }

  // O(E)
  // 任意のサイクル bfs木 -> e{s, t}を min(dep[s], dep[t])の昇順に確かめる
  // iを含む任意のサイクル bfs木 -> e{s, t}s, tのいずれかがiの部分木かつlca(s, t)がiより上
  //
  /*
  vec<edge> undirected_cycle(const vec<int> &cmp, int s = 0){
    static vec<bool> order(n, -1);
    vec<edge> res;
  }
  */
};

using simple_graph = general_graph<simple_edge<int>>;
template<typename T>
using weighted_graph = general_graph<weighted_edge<T>>;
template<typename T>
using labeled_graph =  general_graph<labeled_edge<T>>;
template<typename T>
using weighted_labeled_graph =  general_graph<weighted_labeled_edge<T>>;
#line 4 "a.cpp"

int main(){
  io_init();
  int t;
  std::cin >> t;
  int n, m;
  std::cin >> n >> m;
  weighted_labeled_graph<ll> g(n);

  range(i, 0, m){
    int a, b, c;
    std::cin >> a >> b >> c;
    a--, b--;
    g.add_edge(a, {a, b, c, i});
    if(!t) g.add_edge(b, {b, a, c, i});
  }
  static constexpr ll inf = std::numeric_limits<ll>::max() / 2;

  ll ans = inf;
  range(i, 0, n){
    auto [T, D] = bfs_tree_shortest(g.g, i);
    vec<bool> used(m, false);
    range(j, 0, n) for(auto &e : T.g[j]) used[e.id()] = true;
    if(!t){
      range(j, 0, n){
        for(auto &e : g.g[j]){
          if(used[e.id()] || D[e.from()] == inf || D[e.to()] == inf) continue;
          if(e.from() == e.to()){
            if(e.from() == i) ans = min(ans, e.wei());
            continue;
          }
          ans = min(ans, e.wei() + D[e.from()] + D[e.to()]);
        }
      }
    }else{
      std::cout << D << '\n';
      range(j, 0, n){
        for(auto &e : g.g[j]){
          if(used[e.id()] || D[e.from()] == inf) continue;
          if(e.to() == i){
            ans = min(ans, e.wei() + D[e.from()]);
          }
        }
      }
    }
  }
  std::cout << (ans == inf ? -1 : ans) << '\n';
}