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;
long long Ans;
int N, M, C, D, Rt, st[100005], siz[100005], Max[100005], Bel[100005],
    Cnt[100005];
struct Lin {
  int v, c, next;
} E[100005 * 2];
struct Nod {
  int x, y;
  Nod(int a = 100005 - 1, int b = 100005 - 1) {
    x = a;
    y = b;
  }
  Nod operator+(Nod b) {
    Nod a = *this;
    if (a.x > b.x) swap(a, b);
    if (b.x < a.y && Bel[b.x] != Bel[a.x]) a.y = b.x;
    if (b.y < a.y && Bel[b.y] != Bel[a.x]) a.y = b.y;
    return a;
  }
} T[100005 * 4];
set<int> A[100005], B[100005];
void Link(int u, int v, int c) {
  E[++D] = (Lin){v, c, st[u]};
  st[u] = D;
  E[++D] = (Lin){u, c, st[v]};
  st[v] = D;
}
int DFS1(int u, int f) {
  int rt = 0;
  siz[u] = 1;
  for (int i = st[u], v; i; i = E[i].next)
    if ((v = E[i].v) ^ f) {
      int t = DFS1(v, u);
      if (!rt || Max[t] < Max[rt]) rt = t;
      siz[u] += siz[v];
      Max[u] = max(Max[u], siz[v]);
    }
  Max[u] = max(Max[u], N - siz[u]);
  if (!rt || Max[u] < Max[rt]) rt = u;
  return rt;
}
void DFS2(int u, int f, long long dis) {
  Ans += dis;
  siz[u] = 1;
  for (int i = st[u], v; i; i = E[i].next)
    if ((v = E[i].v) ^ f) DFS2(v, u, dis + E[i].c), siz[u] += siz[v];
}
void DFS3(int u, int f) {
  A[C].insert(u);
  Bel[u] = C;
  for (int i = st[u], v; i; i = E[i].next)
    if ((v = E[i].v) ^ f) DFS3(v, u);
}
void Up(int x) {
  for (x = x + M >> 1; x; x >>= 1) T[x] = T[x << 1] + T[x << 1 | 1];
}
int main() {
  scanf("%d", &N);
  for (int i = 1, u, v, c; i < N; i++)
    scanf("%d%d%d", &u, &v, &c), Link(u, v, c);
  Rt = DFS1(1, 0);
  DFS2(Rt, 0, 0);
  printf("%I64d\n", Ans * 2);
  Bel[100005 - 1] = 100005 - 1;
  for (int i = st[Rt]; i; i = E[i].next)
    B[siz[E[i].v] * 2].insert(++C), Cnt[C] = siz[E[i].v] * 2, DFS3(E[i].v, Rt);
  for (M = 1; M <= N + 1; M <<= 1)
    ;
  for (int i = 1; i <= N; i++) T[M + i] = Nod(i, 100005 - 1);
  for (int i = M; i; i--) T[i] = T[i << 1] + T[i << 1 | 1];
  for (int i = 1; i <= N; i++) {
    int d = N - i + 1, j = 0;
    for (set<int>::iterator t = B[d].begin(); t != B[d].end(); t++)
      if ((*t) != Bel[i]) j = *(A[*t].begin());
    if (!j) (i == Rt || Bel[T[1].x] != Bel[i]) ? j = T[1].x : j = T[1].y;
    if (Cnt[Bel[i]])
      B[Cnt[Bel[i]]].erase(Bel[i]), B[--Cnt[Bel[i]]].insert(Bel[i]);
    if (Cnt[Bel[j]])
      B[Cnt[Bel[j]]].erase(Bel[j]), B[--Cnt[Bel[j]]].insert(Bel[j]);
    A[Bel[j]].erase(j);
    T[M + j] = Nod();
    Up(j);
    printf("%d ", j);
  }
  puts("");
}
