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>
#pragma GCC optimize("Ofast")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
const int nax = 1e5 + 5;
const int inf = 1e9 + 5;
vector<pair<int, int>> w[nax];
int subtree[nax];
long long answer;
const int pot = 128 * 1024;
int tr[2 * pot];
int inv[nax], which_group[nax];
int get_min(int low, int high) {
  if (low > high) return inf;
  low += pot;
  high += pot;
  int r = min(tr[low], tr[high]);
  while (low < high - 1) {
    if (low % 2 == 0) r = min(r, tr[low + 1]);
    if (high % 2) r = min(r, tr[high - 1]);
    low /= 2;
    high /= 2;
  }
  return r;
}
int n;
void dfs(int a, int par) {
  subtree[a] = 1;
  for (pair<int, int> p : w[a]) {
    int b = p.first;
    if (b == par) continue;
    dfs(b, a);
    subtree[a] += subtree[b];
    debug() << " ["
            << "a"
               ": "
            << (a)
            << "] "
               " ["
            << "b"
               ": "
            << (b)
            << "] "
               " ["
            << "subtree[b]"
               ": "
            << (subtree[b])
            << "] "
               " ["
            << "p.second"
               ": "
            << (p.second) << "] ";
    answer += (long long)p.second * min(subtree[b], n - subtree[b]);
  }
}
void dfs_gather(int a, int par, vector<int>& they) {
  they.push_back(a);
  for (pair<int, int> p : w[a])
    if (p.first != par) dfs_gather(p.first, a, they);
}
int main() {
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    puts("1");
    return 0;
  }
  for (int i = 0; i < n - 1; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    w[a].push_back({b, c});
    w[b].push_back({a, c});
  }
  dfs(1, -1);
  int root = 1;
  while (true) {
    bool anything = false;
    for (pair<int, int> p : w[root]) {
      int b = p.first;
      if (subtree[b] < subtree[root] && 2 * subtree[b] >= n) {
        root = b;
        anything = true;
        break;
      }
    }
    if (!anything) break;
  }
  bool is_soft = true;
  for (pair<int, int> p : w[root])
    if (subtree[p.first] * 2 == n) is_soft = false;
  debug() << " ["
          << "is_soft"
             ": "
          << (is_soft) << "] ";
  vector<vector<int>> groups;
  groups.push_back({root});
  for (pair<int, int> p : w[root]) {
    vector<int> they;
    dfs_gather(p.first, root, they);
    groups.push_back(they);
  }
  debug() << " ["
          << "groups"
             ": "
          << (groups) << "] ";
  for (int i = 0; i < 2 * pot; ++i) tr[i] = inf;
  vector<int> starty(groups.size() + 1);
  vector<int> deg(groups.size());
  for (int i = 0; i < (int)groups.size(); ++i) {
    deg[i] = 2 * groups[i].size();
    for (int j = 0; j < (int)groups[i].size(); ++j) {
      int where = pot + starty[i] + j;
      int value = groups[i][j];
      tr[where] = value;
      inv[value] = where - pot;
      which_group[value] = i;
    }
    starty[i + 1] = starty[i] + groups[i].size();
  }
  set<pair<int, int>> secik;
  for (int i = 0; i < (int)groups.size(); ++i) secik.insert({deg[i], i});
  for (int i = pot - 1; i >= 1; --i) tr[i] = min(tr[2 * i], tr[2 * i + 1]);
  printf("%lld\n", answer * 2);
  for (int who = 1; who <= n; ++who) {
    int g = which_group[who];
    int total = 2 * (n - who + 1);
    vector<pair<int, int>> they;
    if (deg[g] * 2 != total && secik.rbegin()->first * 2 == total &&
        !(is_soft && secik.rbegin()->second == which_group[root])) {
      debug() << "A";
      int big = secik.rbegin()->second;
      they.push_back({starty[big], starty[big + 1] - 1});
    } else {
      debug() << "B";
      if (who == root && is_soft) {
        they.push_back({0, starty.back()});
      } else {
        they.push_back({0, starty[g] - 1});
        they.push_back({starty[g + 1], starty.back()});
      }
    }
    int best = inf;
    for (pair<int, int> p : they) best = min(best, get_min(p.first, p.second));
    assert(best != inf);
    int i = inv[best];
    assert(tr[pot + i] == best);
    tr[pot + i] = inf;
    for (int x = (pot + i) / 2; x >= 1; x /= 2)
      tr[x] = min(tr[2 * x], tr[2 * x + 1]);
    assert(which_group[best] != g || (who == root && is_soft));
    for (int gg : {g, which_group[best]}) {
      debug() << "zmniejsz"
                 " ["
              << "gg"
                 ": "
              << (gg) << "] ";
      secik.erase({deg[gg], gg});
      --deg[gg];
      secik.insert({deg[gg], gg});
    }
    printf("%d ", best);
  }
  puts("");
}
