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 = 100010;
int n;
vector<pair<int, int>> e[maxn];
int fa[maxn], z[maxn], zr[maxn];
long long d[maxn];
int c[maxn];
int cc[maxn], ab[maxn];
void dfs(int x, int p) {
  fa[x] = p;
  z[x] = 1;
  zr[x] = 0;
  for (pair<int, int> edge : e[x]) {
    int u = edge.first;
    if (u != p) {
      dfs(u, x);
      z[x] += z[u];
      zr[x] = max(zr[x], z[u]);
    }
  }
  zr[x] = max(zr[x], n - z[x]);
}
set<pair<int, int>, greater<pair<int, int>>> mab;
set<int> nodes[maxn];
set<pair<int, int>> mins;
void color(int x, int p, int col) {
  c[x] = col;
  nodes[col].insert(x);
  for (pair<int, int> edge : e[x]) {
    int u = edge.first;
    if (u != p) {
      d[u] = d[x] + edge.second;
      color(u, x, col);
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; ++i) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    --x, --y;
    e[x].push_back(pair<int, int>(y, w));
    e[y].push_back(pair<int, int>(x, w));
  }
  dfs(0, -1);
  int mind = n, argmind;
  for (int i = 0; i < n; ++i) {
    int d = zr[i];
    if (d < mind) {
      mind = d;
      argmind = i;
    }
  }
  int u = argmind;
  d[u] = 0;
  int nc = 0;
  for (pair<int, int> edge : e[u]) {
    int x = edge.first;
    d[x] = edge.second;
    color(x, u, nc);
    ab[nc] = nodes[nc].size() * 2;
    mab.insert(pair<int, int>(ab[nc], nc));
    mins.insert(pair<int, int>(*nodes[nc].begin(), nc));
    ++nc;
  }
  c[u] = nc;
  nodes[nc].insert(u);
  mins.insert(pair<int, int>(u, nc));
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    ans = ans + d[i];
  }
  printf(
      "%lld"
      "\n",
      ans * 2);
  if (n == 1) {
    puts("1");
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    int ic = c[i];
    int pi;
    auto iter = mab.begin();
    if (*iter == pair<int, int>(n - i, ic)) {
      ++iter;
    }
    int mc;
    if (iter != mab.end() && iter->first == n - i) {
      mc = iter->second;
    } else {
      auto iter = mins.begin();
      if (ic == iter->second && ic != nc) {
        ++iter;
      }
      mc = iter->second;
    }
    assert(ic == nc || mc != ic);
    {
      auto &nodes = ::nodes[mc];
      pi = *nodes.begin();
      mins.erase(mins.find(pair<int, int>(pi, mc)));
      nodes.erase(nodes.begin());
      if (!nodes.empty()) {
        mins.insert(pair<int, int>(*nodes.begin(), mc));
      }
    }
    for (int c : {mc, ic}) {
      if (c != nc) {
        int original_ab = ab[c];
        mab.erase(mab.find(pair<int, int>(original_ab, c)));
        mab.insert(pair<int, int>(ab[c] -= 1, c));
      }
    }
    printf("%d ", pi + 1);
  }
  printf("\n");
  return 0;
}
