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;
const int N = 1e5 + 5;
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + c - '0';
  x *= f;
}
int n, rt;
int head[N], cnt;
int siz[N];
int f[N];
int bel[N], tot;
set<int> S[N], low;
int rest[N];
long long ans;
struct misaka {
  int x, y;
  bool operator<(const misaka &cmp) const {
    if (y != cmp.y)
      return y > cmp.y;
    else
      return x > cmp.x;
  }
};
set<misaka> num;
struct Edge {
  int to, next, w;
} e[N << 1];
void add(int x, int y, int c) {
  e[++cnt] = (Edge){y, head[x], c}, head[x] = cnt;
}
void dfs1(int u, int fa) {
  siz[u] = 1;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (v == fa) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    ans += 2ll * e[i].w * min(siz[v], n - siz[v]);
    f[u] = max(f[u], siz[v]);
  }
  f[u] = max(f[u], n - siz[u]);
}
void dfs2(int u, int fa) {
  siz[u] = 1;
  bel[u] = tot;
  S[tot].insert(u);
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (v == fa) continue;
    dfs2(v, u);
    siz[u] += siz[v];
  }
}
int main() {
  memset(head, -1, sizeof(head));
  read(n);
  for (int i = 1; i <= n - 1; i++) {
    int x, y, c;
    read(x), read(y), read(c);
    add(x, y, c), add(y, x, c);
  }
  dfs1(1, 0);
  rt = 1;
  for (int i = 2; i <= n; i++)
    if (f[i] < f[rt]) rt = i;
  for (int i = head[rt]; ~i; i = e[i].next) {
    int v = e[i].to;
    bel[v] = ++tot;
    dfs2(v, rt);
    rest[tot] = siz[v] * 2;
    low.insert(*S[tot].begin());
    num.insert((misaka){tot, rest[tot]});
  }
  S[0].insert(rt);
  low.insert(rt);
  num.insert((misaka){0, 2});
  rest[0] = 2;
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) {
    int p;
    p = bel[i];
    num.erase(num.lower_bound((misaka){p, rest[p]}));
    rest[p]--;
    num.insert((misaka){p, rest[p]});
    misaka u = *num.begin();
    if (u.y >= n - i + 1 && u.x != bel[i] && u.x)
      p = u.x;
    else {
      set<int>::iterator it = low.begin();
      if (bel[*it] != bel[i] || (*it) == rt)
        ;
      else
        it++;
      p = bel[*it];
    }
    printf("%d ", *S[p].begin());
    low.erase(*S[p].begin());
    S[p].erase(*S[p].begin());
    num.erase(num.lower_bound((misaka){p, rest[p]}));
    rest[p]--;
    if (!S[p].empty()) low.insert(*S[p].begin());
    num.insert((misaka){p, rest[p]});
  }
  puts("");
  return 0;
}
