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;
template <class T>
inline T min(T &a, T &b) {
  return a < b ? a : b;
}
template <class T>
inline T max(T &a, T &b) {
  return a > b ? a : b;
}
template <class T>
void read(T &x) {
  char ch;
  while ((ch = getchar()) && !isdigit(ch))
    ;
  x = ch - '0';
  while ((ch = getchar()) && isdigit(ch)) x = x * 10 + ch - '0';
}
struct point {
  int x, y;
  point() {}
  point(int _x, int _y) : x(_x), y(_y) {}
};
const int N = 120000;
vector<int> E[N], F[N];
set<pair<int, int> > Set;
set<pair<int, int>, greater<pair<int, int> > > Big;
set<pair<int, int> >::iterator It;
set<int> S[N];
queue<int> Q[N];
int size[N], m_sub[N], n, cnt, to[N], An[N], num[N];
long long ans;
void Center(int x, int Fa) {
  size[x] = 1;
  for (int i = 0; i < E[x].size(); i++)
    if (E[x][i] != Fa) {
      Center(E[x][i], x);
      size[x] += size[E[x][i]];
      m_sub[x] = max(m_sub[x], size[E[x][i]]);
    }
  m_sub[x] = max(m_sub[x], n - size[x]);
}
void dfs(int w, int fa, int an) {
  An[w] = an;
  if (an != 0) S[an].insert(w), Q[an].push(w);
  size[w] = 1;
  for (int i = 0; i < E[w].size(); i++)
    if (E[w][i] != fa) {
      if (an == 0)
        dfs(E[w][i], w, ++cnt);
      else
        dfs(E[w][i], w, an);
      size[w] += size[E[w][i]];
      ans += (long long)F[w][i] * size[E[w][i]] * 2LL;
    }
}
void Link(int x, int y) {
  int p = *S[y].begin();
  to[x] = *S[y].begin();
  Set.erase(make_pair(*S[y].begin(), y));
  Big.erase(make_pair(num[y], y));
  if (x != p) Big.erase(make_pair(num[An[x]], An[x]));
  S[y].erase(S[y].begin());
  num[An[x]]--;
  num[y]--;
  if (S[y].size()) Set.insert(make_pair(*S[y].begin(), y));
  Big.insert(make_pair(num[y], y));
  if (x != p) Big.insert(make_pair(num[An[x]], An[x]));
}
void work(int ct) {
  dfs(ct, 0, 0);
  S[0].insert(ct);
  for (int i = 1; i <= cnt; i++) Set.insert(make_pair(*S[i].begin(), i));
  Set.insert(make_pair(ct, 0));
  for (int i = 0; i <= cnt; i++)
    Big.insert(make_pair(S[i].size() * 2, i)), num[i] = S[i].size() * 2;
  int Now = n * 2 + 2;
  for (int i = 1; i <= n; i++) {
    Now -= 2;
    if (Set.size() == 1) {
      Link(i, Set.begin()->second);
      continue;
    }
    if (Big.begin()->first * 2 == Now && Big.begin()->second != An[i] &&
        Big.begin()->second != 0) {
      Link(i, Big.begin()->second);
      continue;
    }
    It = Set.begin();
    if (i != ct && It->second == An[i]) It++;
    Link(i, It->second);
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) printf("%d ", to[i]);
  puts("");
}
int main() {
  scanf("%d", &n);
  int x, y, z;
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d%d", &x, &y, &z);
    E[x].push_back(y);
    E[y].push_back(x);
    F[x].push_back(z);
    F[y].push_back(z);
  }
  Center(1, 0);
  for (int i = 1; i <= n; i++)
    if (m_sub[i] <= n / 2) {
      work(i);
      break;
    }
}
