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 + 5;
vector<pair<int, int>> g[N];
int size[N];
int root_lookup(const int &at, const int &from, const int &n) {
  size[at] = 1;
  int mx_size = -1;
  for (auto &el : g[at]) {
    int to = el.first;
    if (to == from) continue;
    int candidate = root_lookup(to, at, n);
    if (candidate != -1) {
      return candidate;
    }
    size[at] += size[to];
    mx_size = max(mx_size, size[to]);
  }
  if (from != -1) {
    int sz = n - size[at];
    mx_size = max(mx_size, sz);
  }
  if (mx_size <= n / 2) {
    return at;
  }
  return -1;
}
void dfs(int at, int from, const long long d, long long &ans) {
  ans += d;
  for (auto &el : g[at]) {
    int to = el.first;
    int w = el.second;
    if (to != from) {
      dfs(to, at, d + w, ans);
    }
  }
}
const int D = 303;
int num[N];
void walk(int at, int from, int id, set<int> &s) {
  num[at] = id;
  s.insert(at);
  for (auto &el : g[at]) {
    int to = el.first;
    if (to != from) {
      walk(to, at, id, s);
    }
  }
}
int p[N];
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int _n(n - 1), i(0); i < _n; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    --x, --y;
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }
  int root = root_lookup(0, -1, n);
  assert(root != -1);
  long long ans = 0;
  dfs(root, -1, 0, ans);
  cout << 2 * ans << endl;
  vector<set<int>> s(g[root].size() + 1);
  int id = 0;
  for (auto &el : g[root]) {
    int ch = el.first;
    walk(ch, root, id, s[id]);
    ++id;
  }
  num[root] = id;
  s.back().insert(root);
  vector<set<int>> block(((int)s.size() + D - 1) / D);
  for (int _n((int)s.size()), i(0); i < _n; i++)
    for (auto j : s[i]) block[i / D].insert(j);
  set<pair<int, int>> sz;
  vector<int> cnt;
  for (int _n((int)s.size()), i(0); i < _n; i++) {
    cnt.push_back(i == (int)s.size() - 1 ? -2 * N : 2 * (int)s[i].size());
    sz.insert(make_pair(cnt[i], i));
  }
  int m = n;
  for (int _n(n), i(0); i < _n; i++) {
    if (sz.rbegin()->first == m && num[i] != sz.rbegin()->second) {
      p[i] = *s[sz.rbegin()->second].begin();
    } else {
      p[i] = N;
      for (int _n((int)block.size()), j(0); j < _n; j++) {
        if (j != num[i] / D || i == root) {
          if (!block[j].empty()) {
            p[i] = min(p[i], *block[j].begin());
          }
        } else {
          for (int _n(min(D, (int)s.size() - j * D)), k(0); k < _n; k++) {
            if (j * D + k != num[i]) {
              if (!s[j * D + k].empty()) {
                p[i] = min(p[i], *s[j * D + k].begin());
              }
            }
          }
        }
      }
    }
    sz.erase(make_pair(cnt[num[i]], num[i]));
    cnt[num[i]]--;
    sz.insert(make_pair(cnt[num[i]], num[i]));
    sz.erase(make_pair(cnt[num[p[i]]], num[p[i]]));
    cnt[num[p[i]]]--;
    sz.insert(make_pair(cnt[num[p[i]]], num[p[i]]));
    m--;
    s[num[p[i]]].erase(p[i]);
    block[num[p[i]] / D].erase(p[i]);
  }
  for (int _n(n), i(0); i < _n; i++) cout << p[i] + 1 << " ";
  cout << endl;
  return 0;
}
