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 + 2;
long long ans, dis[N];
int res[N], be[N], num[N], val[N << 1], block, n, head[N], dot[N << 1],
    nxt[N << 1], cnt, maxx[N], siz[N], root;
set<int> s[N];
set<pair<int, int> > a, b;
void addEdge(const int u, const int v, const int w) {
  dot[++cnt] = v;
  nxt[cnt] = head[u];
  val[cnt] = w;
  head[u] = cnt;
}
void makeRoot(const int x, const int ba) {
  siz[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int v = dot[i];
    if (v == ba) continue;
    makeRoot(v, x);
    siz[x] += siz[v];
    maxx[x] = max(maxx[x], siz[v]);
  }
  maxx[x] = max(maxx[x], n - siz[x]);
  if (maxx[root] > maxx[x]) root = x;
}
void init(const int x, const int ba, const int blo) {
  if (blo) be[x] = blo, s[blo].insert(x);
  ans += (dis[x] << 1);
  for (int i = head[x]; i; i = nxt[i]) {
    int v = dot[i];
    if (v == ba) continue;
    dis[v] = dis[x] + val[i];
    if (blo)
      init(v, x, blo);
    else
      init(v, x, ++block);
  }
}
void link(const int x, const int y) {
  int tmp = *s[y].begin();
  b.erase(pair<int, int>(num[be[x]], be[x]));
  b.erase(pair<int, int>(num[y], y));
  a.erase(pair<int, int>(tmp, y));
  res[x] = tmp;
  s[y].erase(tmp);
  if (!s[y].empty()) a.insert(pair<int, int>(*s[y].begin(), y));
  --num[be[x]];
  --num[y];
  b.insert(pair<int, int>(num[be[x]], be[x]));
  b.insert(pair<int, int>(num[y], y));
}
int main() {
  int u, v, w;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    scanf("%d %d %d", &u, &v, &w);
    addEdge(u, v, w);
    addEdge(v, u, w);
  }
  maxx[0] = n;
  makeRoot(1, 0);
  init(root, 0, 0);
  s[0].insert(root);
  for (int i = 0; i <= block; ++i) {
    a.insert(pair<int, int>(*s[i].begin(), i));
    num[i] = (int(s[i].size()) << 1);
    b.insert(pair<int, int>(num[i], i));
  }
  for (int i = 1; i <= n; ++i) {
    if (b.rbegin()->first == n - i + 1 && b.rbegin()->second != be[i] &&
        b.rbegin()->second != 0)
      link(i, b.rbegin()->second);
    else {
      set<pair<int, int> >::iterator it = a.begin();
      if (i != root && it->second == be[i]) ++it;
      link(i, it->second);
    }
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; ++i) printf("%d%c", res[i], (i == n ? '\n' : ' '));
  return 0;
}
