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>
const int N = 100005;
int n, head[N], tot;
struct edge {
  int to, nxt, cost;
} e[N << 1];
void link(int x, int y, int w) {
  e[++tot] = (edge){y, head[x], w}, head[x] = tot;
  e[++tot] = (edge){x, head[y], w}, head[y] = tot;
}
long long ans = 0;
int root = -233;
int size[N];
int dfs0(int x, int f = 0) {
  int max = 0;
  size[x] = 1;
  for (int i = head[x]; i; i = e[i].nxt)
    if (e[i].to != f) {
      int ret = dfs0(e[i].to, x);
      ans += 2LL * e[i].cost * std::min(ret, n - ret);
      max = std::max(max, ret), size[x] += ret;
    }
  max = std::max(max, n - size[x]);
  if (max <= n / 2) root = x;
  return size[x];
}
std::set<int> points[N], min;
std::set<std::pair<int, int>, std::greater<std::pair<int, int>>> set;
int bel[N], sum[N];
void dfs1(int x, int s, int f = 0) {
  points[s].emplace(x), bel[x] = s;
  for (int i = head[x]; i; i = e[i].nxt)
    if (e[i].to != f) dfs1(e[i].to, s, x);
}
void link(int x, int y) {
  min.erase(y);
  if (x != root) {
    set.erase({sum[bel[x]], bel[x]});
    set.emplace(--sum[bel[x]], bel[x]);
  }
  if (y != root) {
    set.erase({sum[bel[y]], bel[y]});
    set.emplace(--sum[bel[y]], bel[y]);
    points[bel[y]].erase(y);
    if (points[bel[y]].size()) min.emplace(*points[bel[y]].begin());
  }
}
int solve(int p) {
  int ret;
  if (set.begin()->first == n - p + 1 && bel[p] != set.begin()->second)
    ret = *points[set.begin()->second].begin();
  else
    ret = p == root || bel[*min.begin()] != bel[p] ? *min.begin()
                                                   : *++min.begin();
  return link(p, ret), ret;
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n;
  for (int i = 1, x, y, z; i < n; ++i) std::cin >> x >> y >> z, link(x, y, z);
  dfs0(1), std::cout << ans << '\n';
  min.insert(root);
  for (int i = head[root]; i; i = e[i].nxt) {
    dfs1(e[i].to, e[i].to, root);
    set.emplace(sum[e[i].to] = points[e[i].to].size() * 2, e[i].to);
    min.emplace(*points[e[i].to].begin());
  }
  for (int i = 1; i <= n; ++i) std::cout << solve(i) << ' ';
  return std::cout << '\n', 0;
}
