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;
inline int read() {
  int res = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
  return res;
}
int n;
struct edge {
  int nxt, to, val;
} ed[100005 * 2];
int head[100005], cnt;
inline void add(int x, int y, int z) {
  ed[++cnt] = (edge){head[x], y, z};
  head[x] = cnt;
}
long long ans;
int siz[100005], root, mrt = 1e9;
void dfs(int x, int fa) {
  siz[x] = 1;
  int tmp = 0;
  for (register int i = head[x]; i; i = ed[i].nxt) {
    int to = ed[i].to;
    if (to == fa) continue;
    dfs(to, x);
    siz[x] += siz[to];
    tmp = max(tmp, siz[to]);
  }
  tmp = max(tmp, n - siz[x]);
  if (tmp < mrt) mrt = tmp, root = x;
}
void gfs(int x, int fa, long long d) {
  ans += d;
  for (register int i = head[x]; i; i = ed[i].nxt) {
    int to = ed[i].to;
    if (to == fa) continue;
    gfs(to, x, d + ed[i].val);
  }
}
set<int> all;
set<int> tr[100005];
set<pair<int, int> > inout;
int belong[100005], sum[100005];
void ffs(int x, int fa, int bel) {
  belong[x] = bel;
  tr[bel].insert(x);
  siz[x] = 1;
  for (register int i = head[x]; i; i = ed[i].nxt) {
    int to = ed[i].to;
    if (to == fa) continue;
    ffs(to, x, bel);
    siz[x] += siz[to];
  }
}
inline int Find(int x) {
  set<pair<int, int> >::iterator it =
      inout.lower_bound(make_pair(n - x + 1, 0));
  bool must = 0;
  if (it != inout.end() and (*it).first == n - x + 1 and
      (*it).second != belong[x])
    must = 1;
  if (belong[x]) {
    inout.erase(make_pair(sum[belong[x]], belong[x]));
    sum[belong[x]]--;
    inout.insert(make_pair(sum[belong[x]], belong[x]));
  }
  if (must) {
    int k = *tr[(*it).second].begin();
    all.erase(k);
    tr[(*it).second].erase(k);
    if (tr[(*it).second].size()) all.insert(*tr[(*it).second].begin());
    inout.erase(make_pair(sum[belong[k]], belong[k]));
    inout.insert(make_pair(--sum[belong[k]], belong[k]));
    return k;
  } else {
    set<int>::iterator itt = all.begin();
    if (belong[*itt] == belong[x] and x != root) itt++;
    all.erase(itt);
    int k = *itt;
    if (belong[k]) {
      tr[belong[k]].erase(k);
      if (tr[belong[k]].size()) all.insert(*tr[belong[k]].begin());
      inout.erase(make_pair(sum[belong[k]], belong[k]));
      inout.insert(make_pair(--sum[belong[k]], belong[k]));
    }
    return k;
  }
  return 0;
}
int main() {
  n = read();
  for (register int i = 1; i < n; i++) {
    int x = read(), y = read(), z = read();
    add(x, y, z), add(y, x, z);
  }
  root = 1;
  dfs(1, 0);
  ans = 0;
  gfs(root, 0, 0);
  printf("%lld\n", ans * 2);
  all.insert(root);
  for (register int i = head[root]; i; i = ed[i].nxt) {
    int to = ed[i].to;
    ffs(to, root, to);
    sum[to] = siz[to] * 2;
    inout.insert(make_pair(sum[to], to));
    siz[root] += siz[to];
    all.insert(*tr[to].begin());
  }
  for (register int i = 1; i <= n; i++) printf("%d ", Find(i));
  return 0;
}
