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, head[100010], o = 0, sz[100010], rt = 0, mx[100010], bel[100010];
long long dis[100010], ans;
set<int> all[100010], mn;
set<pair<int, int> > s;
struct edge {
  int to, link, w;
} e[200010];
void add_edge(int u, int v, int w) {
  e[++o].to = v, e[o].link = head[u], head[u] = o, e[o].w = w;
  e[++o].to = u, e[o].link = head[v], head[v] = o, e[o].w = w;
}
void dfs(int u, int pre) {
  sz[u] = 1;
  for (int i = head[u]; i; i = e[i].link) {
    if (e[i].to == pre) continue;
    dis[e[i].to] = dis[u] + e[i].w;
    dfs(e[i].to, u);
    mx[u] = max(mx[u], sz[e[i].to]);
    sz[u] += sz[e[i].to];
  }
  mx[u] = max(mx[u], n - sz[u]);
  if (mx[u] < mx[rt] || !rt) rt = u;
}
void dfs(int u, int pre, int now) {
  bel[u] = now;
  if (bel[u]) all[bel[u]].insert(u);
  for (int i = head[u]; i; i = e[i].link) {
    if (e[i].to == pre) continue;
    dfs(e[i].to, u, now ? now : e[i].to);
    if (u == rt) {
      s.insert(make_pair(sz[e[i].to] = all[e[i].to].size() * 2, e[i].to));
      mn.insert(*all[e[i].to].begin());
    }
  }
}
int find(int now) {
  int res;
  if ((*s.rbegin()).first == n - now + 1 && (*s.rbegin()).second != bel[now]) {
    res = *all[(*s.rbegin()).second].begin();
  } else {
    res = (bel[*mn.begin()] != bel[now] || rt == now) ? *mn.begin()
                                                      : *next(mn.begin());
  }
  mn.erase(res);
  if (bel[now]) {
    s.erase(make_pair(sz[bel[now]], bel[now]));
    sz[bel[now]]--;
    s.insert(make_pair(sz[bel[now]], bel[now]));
  }
  if (bel[res]) {
    all[bel[res]].erase(res);
    if (!all[bel[res]].empty()) mn.insert(*all[bel[res]].begin());
    s.erase(make_pair(sz[bel[res]], bel[res]));
    sz[bel[res]]--;
    s.insert(make_pair(sz[bel[res]], bel[res]));
  }
  return res;
}
int main() {
  scanf("%d", &n);
  if (n == 1) return puts("0\n1"), 0;
  for (int i = 1, u, v, w; i < n; i++)
    scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
  dfs(1, 0);
  dis[rt] = 0;
  dfs(rt, 0);
  for (int i = 1; i <= n; i++) ans += 2 * dis[i];
  printf("%lld\n", ans);
  dfs(rt, 0, 0), mn.insert(rt);
  for (int i = 1; i <= n; i++) printf("%d ", find(i));
}
