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>
using namespace std;
template <class T>
inline void qread(T& x) {
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  if (f) x = -x;
}
inline long long qread() {
  long long x = 0;
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  return f ? -x : x;
}
template <class T>
inline T Max(const T x, const T y) {
  return x > y ? x : y;
}
template <class T>
inline T Min(const T x, const T y) {
  return x < y ? x : y;
}
template <class T>
inline T fab(const T x) {
  return x > 0 ? x : -x;
}
inline long long gcd(const long long a, const long long b) {
  return b ? gcd(b, a % b) : a;
}
inline void getInv(long long inv[], const long long lim, const long long MOD) {
  inv[0] = inv[1] = 1;
  for (long long i = 2; i <= lim; ++i)
    inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
}
template <class T>
void fwrit(const T x) {
  if (x < 0) return (void)(putchar('-'), fwrit(-x));
  if (x > 9) fwrit(x / 10);
  putchar(x % 10 ^ 48);
}
inline long long mulMod(const long long a, const long long b,
                        const long long mod) {
  return ((a * b - (long long)((long double)a / mod * b + 1e-8) * mod) % mod +
          mod) %
         mod;
}
const long long MAXN = 1e5;
struct edge {
  long long to, nxt, w;
  edge(const long long T = 0, const long long N = 0, const long long W = 0)
      : to(T), nxt(N), w(W) {}
} e[(MAXN << 1) + 5];
long long tail[MAXN + 5], ecnt;
inline void add_edge(const long long u, const long long v, const long long w) {
  e[++ecnt] = edge(v, tail[u], w);
  tail[u] = ecnt;
  e[++ecnt] = edge(u, tail[v], w);
  tail[v] = ecnt;
}
long long n, siz[MAXN + 5], dis[MAXN + 5], fa[MAXN + 5];
long long rt, tsize = (1 << 30) - 1, ans1;
inline void dfs(const long long u, const long long ff) {
  siz[u] = 1;
  long long maxx = 0;
  for (long long i = tail[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) != ff) {
      dfs(v, u);
      siz[u] += siz[v];
      maxx = Max(maxx, siz[v]);
    }
  maxx = Max(maxx, n - siz[u]);
  if (maxx < tsize) rt = u, tsize = maxx;
}
inline void dfs(const long long u) {
  ans1 += dis[u];
  for (long long i = tail[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) != fa[u]) {
      dis[v] = dis[fa[v] = u] + e[i].w;
      dfs(v);
    }
}
long long bel[MAXN + 5];
set<long long> in[MAXN + 5];
set<long long> minn;
set<pair<long long, long long> > Set;
inline void init_tre(const long long u, const long long top) {
  in[bel[u] = top].insert(u);
  for (long long i = tail[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) != fa[u]) init_tre(v, top);
}
inline void link(const long long from, const long long to) {
  long long x = bel[from], y = bel[to];
  minn.erase(to);
  if (x) {
    Set.erase(make_pair(siz[x], x));
    Set.insert(make_pair(--siz[x], x));
  }
  if (y) {
    in[y].erase(to);
    if (!in[y].empty()) minn.insert(*in[y].begin());
    Set.erase(make_pair(siz[y], y));
    Set.insert(make_pair(--siz[y], y));
  }
}
inline long long solve(const long long ind) {
  long long ret;
  if (Set.rbegin()->first == n - ind + 1 && Set.rbegin()->second != bel[ind])
    ret = *in[Set.rbegin()->second].begin();
  else
    ret = (bel[ind] != bel[*minn.begin()] || ind == rt) ? (*minn.begin())
                                                        : (*next(minn.begin()));
  link(ind, ret);
  return ret;
}
bool vis[MAXN + 5];
signed main() {
  for (long long i = n = qread(), u, v; i > 1; --i) {
    qread(u), qread(v);
    add_edge(u, v, qread());
  }
  dfs(1, 0);
  dfs(rt);
  fwrit(ans1 << 1), putchar('\n');
  if (n == 1) return puts("1"), 0;
  minn.insert(rt);
  for (long long i = tail[rt], v; i; i = e[i].nxt) {
    v = e[i].to;
    init_tre(v, v);
    minn.insert(*in[v].begin());
    Set.insert(make_pair(siz[v] = (in[v].size() << 1), v));
  }
  for (signed i = 1, i_end_ = n; i <= i_end_; ++i)
    fwrit(solve(i)), putchar(' ');
  return 0;
}
