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 = 1e5 + 5;
int N;
vector<pair<int, int> > E[MAXN];
int sz[MAXN];
int mini = MAXN, centroid;
deque<int> nodes[MAXN];
int val[MAXN], who[MAXN];
long long sol;
struct cmp1 {
  bool operator()(const int &lhs, const int &rhs) const {
    return nodes[lhs].front() < nodes[rhs].front();
  }
};
struct cmp2 {
  bool operator()(const int &lhs, const int &rhs) const {
    if (val[lhs] == val[rhs]) return lhs < rhs;
    return val[lhs] < val[rhs];
  }
};
set<int, cmp1> S1;
set<int, cmp2> S2;
void load() {
  scanf("%d", &N);
  for (int i = 1; i < N; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    E[a].push_back({b, c});
    E[b].push_back({a, c});
  }
}
void dfs(int x, int p) {
  sz[x] = 1;
  int mx = 0;
  for (auto it : E[x])
    if (it.first != p) {
      dfs(it.first, x);
      mx = max(mx, sz[it.first]);
      sz[x] += sz[it.first];
      sol += 2ll * it.second * min(sz[it.first], N - sz[it.first]);
    }
  mx = max(mx, N - sz[x]);
  if (mx < mini) {
    mini = mx;
    centroid = x;
  }
}
void go(int x, int p, int root) {
  nodes[root].push_back(x);
  who[x] = root;
  if (x == centroid) return;
  for (auto it : E[x])
    if (it.first != p) go(it.first, x, root);
}
void update(int x) {
  S2.erase(x);
  val[x]++;
  S2.insert(x);
}
void add(int x, int y) {
  printf("%d ", nodes[y].front());
  update(x);
  update(y);
  S1.erase(y);
  nodes[y].pop_front();
  if (!nodes[y].empty()) S1.insert(y);
}
void connect(int x) {
  auto it = S2.begin();
  for (int i = 0; i < 2 && it != S2.end(); i++) {
    if (*it != who[x] && val[*it] == x - 1) {
      add(who[x], *it);
      return;
    }
    it++;
  }
  auto it1 = S1.begin();
  for (int i = 0; i < 2 && it1 != S1.end(); i++) {
    if (x == centroid || *it1 != who[x]) {
      add(who[x], *it1);
      return;
    }
    it1++;
  }
}
void solve() {
  dfs(1, 0);
  E[centroid].push_back({centroid, 0});
  for (auto it : E[centroid]) {
    int tmp = it.first;
    go(tmp, centroid, tmp);
    sort(nodes[tmp].begin(), nodes[tmp].end());
    val[tmp] = tmp == centroid ? MAXN : N - 2 * (int)nodes[tmp].size();
    S1.insert(tmp);
    S2.insert(tmp);
  }
  printf("%lld\n", sol);
  for (int i = 1; i <= N; i++) connect(i);
  puts("");
}
int main() {
  load();
  solve();
  return 0;
}
