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;
inline int readint() {
  int x;
  scanf("%d", &x);
  return x;
}
struct Edge {
  int to, nxt, val;
  Edge(int T = 0, int N = 0, int V = 0) { to = T, nxt = N, val = V; }
};
const int MaxN = 100005;
Edge edge[MaxN << 1];
int head[MaxN], n, cntEdge;
void addEdge(int a, int b, int c) {
  edge[cntEdge] = Edge(b, head[a], c);
  head[a] = cntEdge++;
  edge[cntEdge] = Edge(a, head[b], c);
  head[b] = cntEdge++;
}
void input() {
  n = readint();
  for (int i = 1; i <= n; ++i) head[i] = -1;
  for (int i = 1, a, b; i < n; ++i) {
    a = readint(), b = readint();
    addEdge(a, b, readint());
  }
}
int bel[MaxN], size[MaxN], root;
long long ans;
void dfs(int x, int pre, long long depth, int b) {
  ans += depth << 1, bel[x] = b, size[x] = 1;
  for (int i = head[x]; ~i; i = edge[i].nxt)
    if (edge[i].to != pre) {
      dfs(edge[i].to, x, depth + edge[i].val, b);
      size[x] += size[edge[i].to];
    }
  if (root == 0) {
    int mx = n - size[x];
    for (int i = head[x]; ~i; i = edge[i].nxt)
      if (edge[i].to != pre) mx = max(mx, size[edge[i].to]);
    if (mx <= (n >> 1)) root = x;
  }
}
set<pair<int, int>> pq;
set<int> tree[MaxN], all;
int deg[MaxN];
void solve() {
  dfs(1, -1, 0, -1);
  ans = 0, dfs(root, -1, 0, -1);
  printf("%lld\n", ans);
  for (int i = head[root]; ~i; i = edge[i].nxt)
    dfs(edge[i].to, root, 0, edge[i].to);
  bel[root] = root;
  for (int i = 1; i <= n; ++i) tree[bel[i]].insert(i);
  all.insert(root);
  for (int i = head[root]; ~i; i = edge[i].nxt) {
    int x = edge[i].to;
    deg[x] = tree[x].size() << 1;
    pq.insert(make_pair(deg[x], x));
    all.insert(*tree[x].begin());
  }
  for (int i = 1, match; i <= n; ++i) {
    auto it = pq.end();
    if (not pq.empty()) --it;
    if (not pq.empty() and it->first == n - i + 1 and it->second != bel[i])
      match = *tree[it->second].begin();
    else {
      auto j = all.begin();
      if (bel[*j] == bel[i] and i != root and *j != root) ++j;
      match = *j;
    }
    printf("%d ", match);
    tree[bel[match]].erase(match);
    all.erase(match);
    pq.erase(make_pair(deg[bel[i]], bel[i]));
    pq.insert(make_pair(--deg[bel[i]], bel[i]));
    pq.erase(make_pair(deg[bel[match]], bel[match]));
    pq.insert(make_pair(--deg[bel[match]], bel[match]));
    if (not tree[bel[match]].empty()) all.insert(*tree[bel[match]].begin());
  }
  puts("");
}
int main() {
  input(), solve();
  return 0;
}
