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, M = 2 * N;
int read() {
  char c = getchar();
  int k = 0;
  for (; c < 48 || c > 57; c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) k = (k << 3) + (k << 1) + c - 48;
  return k;
}
void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
int n, m, i, j, t, a[N], v[N];
long long ans;
int val, et, he[N], size[N], mp, rt;
struct edge {
  int l, to, v;
} e[M];
void line(int x, int y) {
  e[++et].l = he[x];
  he[x] = et;
  e[et].to = y;
  e[et].v = val;
}
void dfs(int x, int fa) {
  size[x] = 1;
  int mx = 0;
  for (int i = he[x]; i; i = e[i].l) {
    int y = e[i].to;
    if (y == fa) continue;
    dfs(y, x);
    size[x] += size[y];
    ans += (long long)e[i].v * min(size[y], n - size[y]);
    mx = max(mx, size[y]);
  }
  mx = max(mx, n - size[x]);
  if (mx < mp) mp = mx, rt = x;
}
void work(int x, int fa) {
  a[++t] = x;
  v[x] = m;
  for (int i = he[x]; i; i = e[i].l)
    if (e[i].to != fa) work(e[i].to, x);
}
int qt, hq[N];
edge d[N];
void add(int x, int y) {
  d[++qt].l = hq[x];
  hq[x] = qt;
  d[qt].to = y;
}
struct arr {
  int k, x;
};
bool operator<(arr A, arr B) { return A.k < B.k; }
priority_queue<arr> num;
struct heap {
  int p, x;
};
bool operator<(heap A, heap B) { return A.p > B.p; }
priority_queue<heap> q;
int g[N];
void wk(int x) {
  g[x]--;
  num.push((arr){g[x], x});
  write(d[hq[x]].to), putchar(' ');
  hq[x] = d[hq[x]].l;
  if (hq[x]) q.push((heap){d[hq[x]].to, x});
}
int main() {
  for (n = read(), i = 1; i < n; i++) {
    int x = read(), y = read();
    val = read();
    line(x, y);
    line(y, x);
  }
  mp = n;
  dfs(1, 0);
  printf("%I64d\n", ans << 1);
  for (i = he[rt]; i; i = e[i].l) {
    t = 0;
    m++;
    work(e[i].to, rt);
    sort(a + 1, a + t + 1);
    for (j = t; j; j--) add(m, a[j]);
    num.push((arr){g[m] = t << 1, m});
    q.push((heap){a[1], m});
  }
  m++;
  add(m, rt);
  g[m] = 1;
  q.push((heap){rt, m});
  for (i = 1; i <= n; i++) {
    int w = v[i];
    g[w]--;
    num.push((arr){g[w], w});
    for (; num.top().k != g[num.top().x]; num.pop())
      ;
    if (num.top().k > n - i) {
      wk(num.top().x);
      continue;
    }
    for (; q.top().p != d[hq[q.top().x]].to; q.pop())
      ;
    if (q.top().x == w && w != m) {
      q.pop();
      for (; q.top().p != d[hq[q.top().x]].to; q.pop())
        ;
      wk(q.top().x);
      q.push((heap){d[hq[w]].to, w});
      continue;
    }
    wk(q.top().x);
  }
}
