Little X has a tree consisting of n nodes (they are numbered from 1 to n). Each edge of the tree has a positive length. Let's define the distance between two nodes v and u (we'll denote it d(v, u)) as the sum of the lengths of edges in the shortest path between v and u. 

A permutation p is a sequence of n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n). Little X wants to find a permutation p such that sum <image> is maximal possible. If there are multiple optimal permutations, he wants to find the lexicographically smallest one. Help him with the task!

Input

The first line contains an integer n (1 ≤ n ≤ 105).

Each of the next n - 1 lines contains three space separated integers ui, vi, wi (1 ≤ ui, vi ≤ n; 1 ≤ wi ≤ 105), denoting an edge between nodes ui and vi with length equal to wi.

It is guaranteed that these edges form a tree.

Output

In the first line print the maximum possible value of the described sum. In the second line print n integers, representing the lexicographically smallest permutation.

Examples

Input

2
1 2 3


Output

6
2 1


Input

5
1 2 2
1 3 3
2 4 4
2 5 5


Output

32
2 1 4 5 3
#include <bits/stdc++.h>
struct Union {
  std::vector<int> P;
  Union(int n) : P(n) {
    for (int i = 0; i < (n); ++i) P[i] = i;
  }
  int get(int i) { return P[i] == i ? i : (P[i] = get(P[i])); }
  int join(int i, int j) { return P[get(i)] = get(j); }
  int size() { return P.size(); }
};
struct Edge {
  int b, w;
};
std::vector<std::vector<Edge>> G;
struct IOQueue {
  std::vector<int> io;
  struct Pair {
    int io, u;
    bool operator<(const Pair &p) const { return io < p.io; }
  };
  std::priority_queue<Pair> queue;
  IOQueue(const std::vector<std::vector<int>> &sets) : io(sets.size()) {
    for (int u = 0; u < (sets.size()); ++u) {
      io[u] = 2 * sets[u].size();
      queue.push(Pair{2 * int(sets[u].size()), u});
    }
  }
  Pair top() {
    while (queue.top().io != io[queue.top().u]) queue.pop();
    return queue.top();
  }
  void dec(int u) { queue.push(Pair{--io[u], u}); }
};
struct LQueue {
  std::vector<std::vector<int>> sets;
  struct Pair {
    int i, u;
    bool operator<(const Pair &p) const { return i > p.i; }
  };
  std::priority_queue<Pair> queue;
  LQueue(Union &U) : sets(U.size()) {
    for (int i = (U.size() - 1); i >= (0); --i) sets[U.get(i)].push_back(i);
    for (int u = 0; u < (sets.size()); ++u)
      if (sets[u].size()) queue.push(Pair{sets[u].back(), u});
  }
  int pop(int u) {
    int i = sets[u].back();
    sets[u].pop_back();
    if (sets[u].size()) queue.push(Pair{sets[u].back(), u});
    return i;
  }
  int top() {
    while (1) {
      Pair p = queue.top();
      if (sets[p.u].size() && sets[p.u].back() == p.i) break;
      queue.pop();
    }
    return queue.top().u;
  }
  int other(int u) {
    while (top() == u) queue.pop();
    int v = top();
    if (sets[u].size()) queue.push(Pair{sets[u].back(), u});
    return v;
  }
};
int main() {
  int n;
  scanf("%d", &n);
  G.resize(n);
  for (int i = 0; i < (n - 1); ++i) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    a--;
    b--;
    G[a].push_back(Edge{b, w});
    G[b].push_back(Edge{a, w});
  }
  if (n == 1) {
    printf("0\n1\n");
    return 0;
  }
  Union U(n);
  std::vector<int> deg_queue, ss(n, -1), deg(n);
  for (int i = 0; i < (n); ++i)
    if ((deg[i] = G[i].size()) == 1) deg_queue.push_back(i);
  int centroid = -1;
  long long res = 0;
  int cc = 0;
  while (deg_queue.size()) {
    int v = deg_queue.back();
    deg_queue.pop_back();
    ss[v] = 1;
    for (Edge e : G[v]) {
      if (ss[e.b] != -1) ss[v] += ss[e.b];
      if (--deg[e.b] == 1) deg_queue.push_back(e.b);
    }
    for (Edge e : G[v])
      if (ss[e.b] == -1) res += 2LL * e.w * std::min(ss[v], n - ss[v]);
    bool ok = n - ss[v] <= n / 2;
    for (Edge e : G[v]) ok &= ss[e.b] <= n / 2;
    if (ok) cc++;
    if (ok && centroid == -1)
      centroid = v;
    else
      for (Edge e : G[v])
        if (ss[e.b] != -1 && e.b != centroid) U.join(e.b, v);
  }
  assert(centroid != -1);
  std::vector<int> R;
  LQueue lq(U);
  IOQueue ioq(lq.sets);
  int c = cc == 1 ? centroid : -1;
  for (int i = 0; i < (n); ++i) {
    int u = U.get(i);
    ioq.dec(u);
    auto p = ioq.top();
    int v = p.io == n - i && p.u != c ? p.u : u == c ? lq.top() : lq.other(u);
    ioq.dec(v);
    R.push_back(lq.pop(v));
  }
  printf("%lld\n", res);
  for (int r : R) printf("%d ", r + 1);
  puts("");
  return 0;
}
