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;
int n, rt, x_, y_, z_;
int siz[1000005], mx[1000005], id[1000005], lft[1000005];
long long ans;
long long dep[1000005];
vector<int> G[1000005], W[1000005];
set<int> in[1000005], glob_min;
set<pair<int, int> > all;
inline void add_edge(int u, int v, int w) {
  G[u].push_back(v);
  W[u].push_back(w);
  G[v].push_back(u);
  W[v].push_back(w);
}
void find_root(int u, int c_fa) {
  siz[u] = 1;
  for (int v : G[u]) {
    if (v == c_fa) continue;
    find_root(v, u);
    siz[u] += siz[v];
    mx[u] = max(mx[u], siz[v]);
  }
  mx[u] = max(mx[u], n - siz[u]);
  if (mx[u] < mx[rt]) rt = u;
}
void dfs(int u, int c_fa) {
  int sz = G[u].size();
  for (int i = 0; i < sz; i++) {
    int v = G[u][i], w = W[u][i];
    if (v == c_fa) continue;
    dep[v] = dep[u] + w;
    ans += 2 * dep[v];
    dfs(v, u);
  }
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    (x *= 10) += ch - '0';
    ch = getchar();
  }
  return x * f;
}
void get(int u, int c_fa, int now) {
  in[now].insert(u);
  id[u] = now;
  for (int v : G[u]) {
    if (v == c_fa) continue;
    get(v, u, now);
  }
}
inline void link(int x, int y) {
  int p = id[x], q = id[y];
  glob_min.erase(y);
  if (p) {
    all.erase({lft[p], p});
    all.insert({--lft[p], p});
  }
  if (q) {
    in[q].erase(y);
    if (!in[q].empty()) glob_min.insert(*in[q].begin());
    all.erase({lft[q], q});
    all.insert({--lft[q], q});
  }
}
inline int find(int x) {
  int res;
  if ((--all.end())->first == n - x + 1 && (--all.end())->second != id[x])
    res = *in[(--all.end())->second].begin();
  else
    res = (id[*glob_min.begin()] != id[x] || x == rt) ? *glob_min.begin()
                                                      : *next(glob_min.begin());
  link(x, res);
  return res;
}
int main() {
  n = read();
  if (n == 1) {
    puts("0");
    puts("1");
    return 0;
  }
  for (int i = 1; i < n; i++)
    x_ = read(), y_ = read(), z_ = read(), add_edge(x_, y_, z_);
  mx[0] = 1e6;
  find_root(1, 1);
  dfs(rt, rt);
  printf("%lld\n", ans);
  glob_min.insert(rt);
  for (int v : G[rt]) {
    get(v, rt, v);
    glob_min.insert(*in[v].begin());
    all.insert(make_pair(lft[v] = in[v].size() * 2, v));
  }
  for (int i = 1; i <= n; i++) printf("%d ", find(i));
  return 0;
}
