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 first = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) {
    if (ch == '-') f = -1;
  }
  for (; isdigit(ch); ch = getchar()) {
    first = first * 10 + ch - 48;
  }
  return first * f;
}
const int mxN = 1e5;
int n, en, rt, tot;
long long ans;
struct Edge {
  int v, nxt;
  long long w;
} e[mxN * 2 + 3];
int fe[mxN + 3];
int fa[mxN + 3], sz[mxN + 3], dfn[mxN + 3];
set<int> s[mxN + 3];
set<pair<int, int> > s2, s3;
int cnt[mxN + 3], bel[mxN + 3], p[mxN + 3];
void addedge(int u, int v, long long w) {
  en++;
  e[en].v = v;
  e[en].w = w;
  e[en].nxt = fe[u];
  fe[u] = en;
}
void dfs1(int u) {
  sz[u] = 1;
  for (int i = fe[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa[u]) continue;
    fa[v] = u;
    dfs1(v);
    ans += 2ll * e[i].w * min(sz[v], n - sz[v]);
    sz[u] += sz[v];
  }
}
void dfs2(int u) {
  rt = u;
  for (int i = fe[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa[u]) continue;
    fa[v] = u;
    if (sz[v] * 2 >= n) {
      dfs2(v);
      return;
    }
  }
}
void dfs3(int u, int tfa, int tbel) {
  bel[u] = tbel;
  s[tbel].insert(u);
  for (int i = fe[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == tfa) continue;
    dfs3(v, u, tbel);
  }
}
int main() {
  n = read();
  for (int i = 1; i < n; i++) {
    int u = read(), v = read(), w = read();
    addedge(u, v, w), addedge(v, u, w);
  }
  if (n == 1) {
    printf("0\n1\n");
    return 0;
  }
  dfs1(1);
  dfs2(1);
  s[++tot].insert(rt);
  bel[rt] = 1;
  for (int i = fe[rt]; i; i = e[i].nxt) {
    int u = e[i].v;
    ++tot;
    dfs3(u, rt, tot);
  }
  for (int i = 1; i <= tot; i++) s[i].insert(n + 1);
  for (int i = 1; i <= tot; i++) {
    cnt[i] = 2 * (s[i].size() - 1);
    s2.insert(make_pair(*s[i].begin(), i));
    s3.insert(make_pair(cnt[i], i));
  }
  for (int i = 1; i <= n; i++) {
    int first = bel[i];
    s3.erase(make_pair(cnt[first], first));
    cnt[first]--;
    s3.insert(make_pair(cnt[first], first));
    if (first != 1) {
      s2.erase(make_pair(*s[first].begin(), first));
    }
    int second =
        ((*s3.rbegin()).first == n - i + 1 && (*s3.rbegin()).second != 1)
            ? (*s3.rbegin()).second
            : (*s2.begin()).second;
    p[i] = *s[second].begin();
    s2.erase(make_pair(*s[second].begin(), second));
    s[second].erase(*s[second].begin());
    s2.insert(make_pair(*s[second].begin(), second));
    s3.erase(make_pair(cnt[second], second));
    cnt[second]--;
    s3.insert(make_pair(cnt[second], second));
    if (first != 1) {
      s2.insert(make_pair(*s[first].begin(), first));
    }
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) printf("%d ", p[i]);
  puts("");
  return 0;
}
