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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXM = MAXN - 1;
const int MAXCOMP = MAXN;
const int MAXVAL = MAXN;
int n;
int fst[MAXN];
int nxt[2 * MAXM];
int to[2 * MAXM];
int len[MAXM];
int root;
int sz[MAXN];
void dfs1(int at, int par) {
  sz[at] = 1;
  int maxsz = 0;
  for (int x = fst[at]; x != -1; x = nxt[x]) {
    if (to[x] == par) continue;
    dfs1(to[x], at);
    if (sz[to[x]] > maxsz) maxsz = sz[to[x]];
    sz[at] += sz[to[x]];
  }
  if (n - sz[at] > maxsz) maxsz = n - sz[at];
  if (root == -1 && 2 * maxsz <= n) root = at;
}
int ncomp;
int comp[MAXN];
int compstart[MAXCOMP];
int compsz[MAXCOMP];
int compnodes[MAXN];
int compin[MAXCOMP];
int compout[MAXCOMP];
long long d[MAXN];
void dfs2(int at, int par) {
  comp[at] = ncomp;
  compnodes[compstart[ncomp] + compsz[ncomp]++] = at;
  for (int x = fst[at]; x != -1; x = nxt[x]) {
    if (to[x] == par) continue;
    d[to[x]] = d[at] + len[x / 2];
    dfs2(to[x], at);
  }
}
int out[MAXN], in[MAXN];
int cntcomp[MAXVAL + 1];
int fstcomp[MAXVAL + 1];
int nxtcomp[MAXCOMP];
int prvcomp[MAXCOMP];
int atcomp[MAXCOMP];
int at1, at2;
void insertcomp(int x) {
  int val = compin[x] + compout[x];
  cntcomp[val]++;
  prvcomp[x] = -1;
  nxtcomp[x] = fstcomp[val];
  if (nxtcomp[x] != -1) prvcomp[nxtcomp[x]] = x;
  fstcomp[val] = x;
}
void removecomp(int x) {
  int val = compin[x] + compout[x];
  cntcomp[val]--;
  if (prvcomp[x] != -1)
    nxtcomp[prvcomp[x]] = nxtcomp[x];
  else
    fstcomp[val] = nxtcomp[x];
  if (nxtcomp[x] != -1) prvcomp[nxtcomp[x]] = prvcomp[x];
  prvcomp[x] = nxtcomp[x] = -1;
}
void printcomps() {
  for (int i = (0); i <= (n); ++i)
    if (cntcomp[i] != 0) {
      printf("%d (%d):", i, cntcomp[i]);
      for (int x = fstcomp[i]; x != -1; x = nxtcomp[x]) printf(" %d", x);
      puts("");
    }
}
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) fst[i] = -1;
  for (int i = (0); i < (n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a, --b;
    len[i] = c;
    nxt[2 * i + 0] = fst[a];
    fst[a] = 2 * i + 0;
    to[2 * i + 0] = b;
    nxt[2 * i + 1] = fst[b];
    fst[b] = 2 * i + 1;
    to[2 * i + 1] = a;
  }
  root = -1;
  dfs1(0, -1);
  assert(root != -1);
  ncomp = 0;
  comp[root] = -1;
  d[root] = 0;
  for (int x = fst[root]; x != -1; x = nxt[x]) {
    compstart[ncomp] =
        ncomp == 0 ? 0 : compstart[ncomp - 1] + compsz[ncomp - 1];
    compsz[ncomp] = 0;
    d[to[x]] = len[x / 2];
    dfs2(to[x], root);
    ++ncomp;
  }
  for (int i = (0); i < (ncomp); ++i)
    sort(compnodes + compstart[i], compnodes + compstart[i] + compsz[i]);
  for (int i = (0); i < (ncomp); ++i) compin[i] = compout[i] = compsz[i];
  for (int i = (0); i < (n); ++i) out[i] = in[i] = -1;
  for (int i = (0); i <= (n); ++i) cntcomp[i] = 0, fstcomp[i] = -1;
  for (int i = (0); i < (ncomp); ++i) nxtcomp[i] = prvcomp[i] = -1;
  for (int i = (0); i < (ncomp); ++i) insertcomp(i);
  for (int i = (0); i < (ncomp); ++i) atcomp[i] = 0;
  at1 = at2 = 0;
  int rem = n;
  for (int i = (0); i < (n); ++i) {
    int fixcomp = -1;
    for (int x = fstcomp[rem]; x != -1; x = nxtcomp[x]) {
      if (comp[i] == x) continue;
      assert(fixcomp == -1);
      fixcomp = x;
    }
    int j;
    if (fixcomp != -1) {
      while (atcomp[fixcomp] < compsz[fixcomp] &&
             in[compnodes[compstart[fixcomp] + atcomp[fixcomp]]] != -1)
        ++atcomp[fixcomp];
      assert(atcomp[fixcomp] < compsz[fixcomp]);
      j = compnodes[compstart[fixcomp] + atcomp[fixcomp]];
    } else {
      while (at1 < n && in[at1] != -1) ++at1;
      while (at2 < n && (in[at2] != -1 || at1 < n && comp[at1] == comp[at2]))
        ++at2;
      assert(at1 < n);
      assert(i == root || comp[at1] != comp[i] ||
             at2 < n && comp[at2] != comp[i]);
      j = i == root || comp[at1] != comp[i] ? at1 : at2;
    }
    out[i] = j;
    in[j] = i;
    if (comp[i] != -1) {
      removecomp(comp[i]);
      --compout[comp[i]];
      insertcomp(comp[i]);
    }
    if (comp[j] != -1) {
      removecomp(comp[j]);
      --compin[comp[j]];
      insertcomp(comp[j]);
    }
    --rem;
  }
  long long dsum = 0;
  for (int i = (0); i < (n); ++i) dsum += d[i];
  cout << 2 * dsum << endl;
  for (int i = (0); i < (n); ++i) {
    if (i != 0) printf(" ");
    printf("%d", out[i] + 1);
  }
  puts("");
}
int main() {
  run();
  return 0;
}
