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 = 100005;
long long ans;
int n, T, M, rt, tot;
int head[N], sz[N], mx[N];
int be[N], cnt[N];
set<int> S[N], A[N];
struct edge {
  int to, next, v;
} e[N * 2];
struct node {
  int x, y;
  node operator+(node b) {
    node a = *this;
    if (a.x > b.x) swap(a, b);
    if (b.x < a.y && be[b.x] != be[a.x]) a.y = b.x;
    if (b.y < a.y && be[b.y] != be[a.x]) a.y = b.y;
    return a;
  }
} t[N * 4];
void add(int x, int y, int v) {
  e[++tot] = (edge){y, head[x], v};
  head[x] = tot;
}
void dfs1(int x, int fa) {
  sz[x] = 1;
  mx[x] = 0;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa) {
      dfs1(e[i].to, x);
      sz[x] += sz[e[i].to];
      mx[x] = max(mx[x], sz[e[i].to]);
    }
  mx[x] = max(mx[x], n - sz[x]);
  if (!rt || mx[x] < mx[rt]) rt = x;
}
void dfs2(int x, int fa, long long dep) {
  ans += dep;
  sz[x] = 1;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa) {
      dfs2(e[i].to, x, dep + e[i].v);
      sz[x] += sz[e[i].to];
    }
}
void dfs3(int x, int fa) {
  A[T].insert(x);
  be[x] = T;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa) dfs3(e[i].to, x);
}
void pushup(int x) {
  for (x = (x + M) / 2; x; x /= 2) t[x] = t[x * 2] + t[x * 2 + 1];
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n - 1); i++) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    add(x, y, v);
    add(y, x, v);
  }
  dfs1(1, 0);
  dfs2(rt, 0, 0);
  printf("%lld\n", ans * 2);
  for (int i = head[rt]; i; i = e[i].next) {
    S[sz[e[i].to] * 2].insert(++T);
    cnt[T] = sz[e[i].to] * 2;
    dfs3(e[i].to, rt);
  }
  be[N - 1] = N - 1;
  for (M = 1; M <= n + 1; M <<= 1)
    ;
  M--;
  for (int i = (int)(1); i <= (int)(M * 2 + 1); i++)
    t[i] = (node){N - 1, N - 1};
  for (int i = (int)(1); i <= (int)(n); i++) t[M + i] = (node){i, N - 1};
  for (int i = (int)(M); i >= (int)(1); i--) t[i] = t[i * 2] + t[i * 2 + 1];
  for (int i = (int)(1); i <= (int)(n); i++) {
    int d = n - i + 1, j = 0;
    set<int>::iterator it;
    for (it = S[d].begin(); it != S[d].end(); it++)
      if ((*it) != be[i]) j = *A[*it].begin();
    if (!j) j = ((i == rt || be[t[1].x] != be[i]) ? t[1].x : t[1].y);
    if (cnt[be[i]]) {
      S[cnt[be[i]]].erase(be[i]);
      S[--cnt[be[i]]].insert(be[i]);
    }
    if (cnt[be[j]]) {
      S[cnt[be[j]]].erase(be[j]);
      S[--cnt[be[j]]].insert(be[j]);
    }
    A[be[j]].erase(j);
    t[M + j] = (node){N - 1, N - 1};
    pushup(j);
    printf("%d ", j);
  }
}
