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 n, sum, rt, cnt;
int head[100005], siz[100005], f[100005];
int id[100005], in[100005], out[100005];
long long ans;
set<int> s[100005];
set<pair<int, int> > minx, maxn;
struct node {
  int v;
  int w;
  int nxt;
} a[200005];
void ins(int u, int v, int w) {
  ++sum;
  a[sum].v = v;
  a[sum].w = w;
  a[sum].nxt = head[u];
  head[u] = sum;
  return;
}
void dfs1(int k, int fa) {
  siz[k] = 1;
  int d = head[k];
  while (d) {
    if (a[d].v != fa) {
      dfs1(a[d].v, k);
      siz[k] += siz[a[d].v];
      f[k] = max(f[k], siz[a[d].v]);
    }
    d = a[d].nxt;
  }
  f[k] = max(f[k], n - siz[k]);
  if (f[k] < f[rt]) rt = k;
  return;
}
void dfs2(int k, int fa, long long dep) {
  siz[k] = 1;
  ans += dep;
  int d = head[k];
  while (d) {
    if (a[d].v != fa) {
      dfs2(a[d].v, k, dep + a[d].w);
      siz[k] += siz[a[d].v];
    }
    d = a[d].nxt;
  }
  return;
}
void dfs3(int k, int fa) {
  id[k] = cnt;
  s[cnt].insert(k);
  int d = head[k];
  while (d) {
    if (a[d].v != fa) dfs3(a[d].v, k);
    d = a[d].nxt;
  }
  return;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    ins(u, v, w);
    ins(v, u, w);
  }
  f[0] = n;
  dfs1(1, 0);
  dfs2(rt, 0, 0);
  printf("%lld\n", ans * 2);
  cnt = 1;
  id[rt] = cnt;
  s[cnt].insert(rt);
  in[cnt] = 1;
  out[cnt] = 1;
  minx.insert(make_pair(rt, cnt));
  maxn.insert(make_pair(-2, cnt));
  int d = head[rt];
  while (d) {
    ++cnt;
    in[cnt] = siz[a[d].v];
    out[cnt] = siz[a[d].v];
    dfs3(a[d].v, rt);
    minx.insert(make_pair(*s[cnt].begin(), cnt));
    maxn.insert(make_pair(-(in[cnt] + out[cnt]), cnt));
    d = a[d].nxt;
  }
  for (int i = 1; i <= n; ++i) {
    maxn.erase(maxn.find(make_pair(-(in[id[i]] + out[id[i]]), id[i])));
    --in[id[i]];
    maxn.insert(make_pair(-(in[id[i]] + out[id[i]]), id[i]));
    pair<int, int> top = *maxn.begin();
    if (top.second != 1 && -top.first == n - i + 1) {
      int id = top.second;
      printf("%d ", *s[id].begin());
      --out[id];
      maxn.erase(maxn.begin());
      maxn.insert(make_pair(-(in[id] + out[id]), id));
      minx.erase(minx.find(make_pair(*s[id].begin(), id)));
      s[id].erase(s[id].begin());
      if (!s[id].empty()) minx.insert(make_pair(*s[id].begin(), id));
    } else {
      set<pair<int, int> >::iterator k = minx.begin();
      if (i != rt && (*k).second == id[i]) ++k;
      printf("%d ", (*k).first);
      maxn.erase(maxn.find(
          make_pair(-(in[(*k).second] + out[(*k).second]), (*k).second)));
      --out[(*k).second];
      maxn.insert(
          make_pair(-(in[(*k).second] + out[(*k).second]), (*k).second));
      s[(*k).second].erase(s[(*k).second].begin());
      if (!s[(*k).second].empty())
        minx.insert(make_pair(*s[(*k).second].begin(), (*k).second));
      minx.erase(k);
    }
  }
  return 0;
}
