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 MAXN = 100005;
struct Node {
  int To, Next, Cost;
  Node(void) {}
  Node(int a, int b, int c) : To(a), Next(b), Cost(c) {}
} E[MAXN * 2];
set<int> S[MAXN];
set<pair<int, int> > Ti;
set<pair<int, int>, greater<pair<int, int> > > Count;
long long Len[MAXN], Ans;
int Size[MAXN], Ch[MAXN], Final[MAXN], Num[MAXN], Anc[MAXN], Cnt, N, tot, Root;
void Link(int u, int v, int c) {
  E[++tot] = Node(v, Final[u], c), Final[u] = tot;
}
void Dfs_Size(int Now, int Pre) {
  Size[Now] = 1;
  for (int i = Final[Now]; i; i = E[i].Next)
    if (E[i].To != Pre) Dfs_Size(E[i].To, Now), Size[Now] += Size[E[i].To];
}
void Get_Heavy(int Now, int Pre) {
  bool ok = 1;
  if (N - Size[Now] > N / 2) ok = 0;
  for (int i = Final[Now]; i; i = E[i].Next)
    if (E[i].To != Pre) {
      if (Size[E[i].To] > N / 2) ok = 0;
      Get_Heavy(E[i].To, Now);
    }
  if (ok) Root = Now;
}
void Dfs(int Now, int Pre, int Top) {
  Anc[Now] = Top;
  S[Top].insert(Now);
  if (Top) Num[Top] += 2;
  for (int i = Final[Now]; i; i = E[i].Next)
    if (E[i].To != Pre) {
      Len[E[i].To] = Len[Now] + E[i].Cost;
      Ans += 2 * Len[E[i].To];
      Dfs(E[i].To, Now, (Top) ? Top : (++Cnt));
    }
}
void Link(int l, int p) {
  int c = *(S[p].begin());
  if (l != c) Count.erase(pair<int, int>(Num[Anc[l]], Anc[l]));
  Count.erase(pair<int, int>(Num[p], p)),
      Ti.erase(pair<int, int>(*S[p].begin(), p));
  Ch[l] = c;
  Num[p]--;
  Num[Anc[l]]--;
  S[p].erase(c);
  if (l != c) Count.insert(pair<int, int>(Num[p], p));
  Count.insert(pair<int, int>(Num[Anc[l]], Anc[l]));
  if (S[p].size()) Ti.insert(pair<int, int>(*S[p].begin(), p));
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i < N; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    Link(u, v, c), Link(v, u, c);
  }
  Dfs_Size(1, 0);
  Get_Heavy(1, 0);
  Dfs(Root, 0, 0);
  for (int i = 1; i <= Cnt; i++)
    Ti.insert(pair<int, int>(*S[i].begin(), i)),
        Count.insert(pair<int, int>(Num[i], i));
  Ti.insert(pair<int, int>(Root, 0));
  int Least = N;
  for (int i = 1; i <= N; i++) {
    if ((Count.begin()->first == Least--) &&
        (Anc[i] != (Count.begin()->second))) {
      Link(i, Count.begin()->second);
      continue;
    }
    set<pair<int, int> >::iterator it = Ti.begin();
    if (it->second == Anc[i] && i != Root) it++;
    if (it != Ti.end()) Link(i, it->second);
  }
  printf("%I64d\n", Ans);
  for (int i = 1; i <= N; i++) printf("%d%c", Ch[i], (i == N) ? '\n' : ' ');
  return 0;
}
