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 i, j, k, n, m, mi, ro, t;
int si[100010], L[100010], R[100010], id[100010], tr[100010 * 4], wei[100010];
pair<int, int> c[100010 * 4];
vector<int> root;
vector<pair<int, int> > a[100010], b[100010];
long long an;
void dfs(int x, int y) {
  int i, ma = 0;
  si[x] = 1;
  for (i = 0; i < a[x].size(); i++) {
    pair<int, int> A = a[x][i];
    if (A.first == y) continue;
    dfs(A.first, x);
    int B = si[A.first];
    an += 2ll * A.second * min(B, n - B);
    si[x] += B;
    ma = max(ma, B);
  }
  ma = max(ma, n - si[x]);
  if (ma < mi)
    mi = ma, root.clear(), root.push_back(x);
  else if (ma == mi)
    root.push_back(x);
}
void Dfs(int x, int y, int z) {
  int i;
  L[x] = ++t;
  id[x] = z;
  wei[t] = x;
  si[x] = 1;
  for (i = 0; i < a[x].size(); i++) {
    pair<int, int> A = a[x][i];
    if (A.first == y) continue;
    Dfs(A.first, x, !z ? A.first : z);
    si[x] += si[A.first];
  }
  R[x] = t;
}
inline void update(int x) {
  int y = x * 2, z = x * 2 + 1;
  tr[x] = min(tr[y], tr[z]);
  c[x] = max(c[y], c[z]);
}
void build(int q, int x, int y) {
  if (x == y) {
    tr[q] = wei[x];
    if (id[x] == x) c[q] = make_pair(si[x] * 2, x);
    return;
  }
  int mid = (x + y) / 2;
  build(q * 2, x, mid);
  build(q * 2 + 1, mid + 1, y);
  update(q);
}
void into(int q, int x, int y, int k) {
  if (x == y) {
    tr[q] = 100010;
    return;
  }
  int mid = (x + y) / 2;
  if (k <= mid)
    into(q * 2, x, mid, k);
  else
    into(q * 2 + 1, mid + 1, y, k);
  update(q);
}
int cal(int q, int x, int y, int l, int r) {
  if (l > r) return 100010;
  if (l <= x && y <= r) return tr[q];
  int mid = (x + y) / 2, mi = 100010;
  if (l <= mid) mi = min(mi, cal(q * 2, x, mid, l, r));
  if (mid < r) mi = min(mi, cal(q * 2 + 1, mid + 1, y, l, r));
  return mi;
}
void jian(int q, int x, int y, int k) {
  if (x == y) {
    c[q].first--;
    return;
  }
  int mid = (x + y) / 2;
  if (k <= mid)
    jian(q * 2, x, mid, k);
  else
    jian(q * 2 + 1, mid + 1, y, k);
  update(q);
}
pair<int, int> Cal(int q, int x, int y, int l, int r) {
  if (l > r) return make_pair(0, 0);
  if (l <= x && y <= r) return c[q];
  int mid = (x + y) / 2;
  pair<int, int> ma;
  ma = make_pair(0, 0);
  if (l <= mid) ma = max(ma, Cal(q * 2, x, mid, l, r));
  if (mid < r) ma = max(ma, Cal(q * 2 + 1, mid + 1, y, l, r));
  return ma;
}
int main() {
  scanf("%d", &n);
  if (n == 1) {
    printf("0\n1\n");
    return 0;
  }
  for (i = 1; i <= n - 1; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    a[x].push_back(make_pair(y, z));
    a[y].push_back(make_pair(x, z));
  }
  mi = 100010;
  dfs(1, 0);
  printf("%I64d\n", an);
  ro = root[0];
  Dfs(ro, 0, 0);
  for (i = 1; i <= n; i++)
    if (i == ro) {
      if (root.size() == 2) {
        int A = root[1];
        b[i].push_back(make_pair(L[A], R[A]));
      } else
        b[i].push_back(make_pair(1, n));
    } else {
      int A = id[i];
      b[i].push_back(make_pair(1, L[A] - 1));
      b[i].push_back(make_pair(R[A] + 1, n));
    }
  build(1, 1, n);
  for (i = 1; i <= n; i++) {
    int mi = 100010;
    for (j = 0; j < b[i].size(); j++) {
      pair<int, int> A = b[i][j];
      mi = min(mi, cal(1, 1, n, A.first, A.second));
    }
    int F = 0;
    {
      pair<int, int> A;
      if (id[i])
        A = max(Cal(1, 1, n, 1, id[i] - 1), Cal(1, 1, n, id[i] + 1, n));
      else
        A = c[1];
      int sh = n - i + 1;
      if (sh == A.first) mi = cal(1, 1, n, L[A.second], R[A.second]), F = 1;
    }
    printf("%d ", mi);
    into(1, 1, n, L[mi]);
    if (id[mi]) jian(1, 1, n, id[mi]);
    if (id[i]) jian(1, 1, n, id[i]);
  }
  printf("\n");
  return 0;
}
