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 N = 2e5 + 5;
set<int> S[N];
vector<int> E[N], W[N], V[N];
int n, root, cnt, size[N], belong[N], sum[N];
long long ans, dis[N];
void dfs(int first, int f) {
  size[first] = 1;
  int m = 0;
  for (int i = E[first].size() - 1; i >= 0; i--) {
    int u = E[first][i];
    if (u == f) continue;
    dfs(u, first);
    m = max(m, size[u]);
    size[first] += size[u];
  }
  m = max(m, n - size[first]);
  if (m <= n / 2) root = first;
}
void dfs1(int first, int f, long long second) {
  dis[first] = second;
  for (int i = E[first].size() - 1; i >= 0; i--) {
    int u = E[first][i], w = W[first][i];
    if (u == f) continue;
    dfs1(u, first, second + w);
  }
}
void dfs2(int first, int f) {
  sum[cnt]++;
  belong[first] = cnt;
  S[cnt].insert(first);
  for (int i = E[first].size() - 1; i >= 0; i--) {
    int u = E[first][i];
    if (u == f) continue;
    dfs2(u, first);
  }
}
pair<int, int> Max[N << 2], Min[N << 2];
inline void update(int &k) {
  Max[k] = max(Max[k << 1], Max[k << 1 | 1]);
  Min[k] = min(Min[k << 1], Min[k << 1 | 1]);
}
void Ins(int k, int l, int r, int p, int re, int id) {
  if (l == r) {
    Max[k] = make_pair(re, p);
    Min[k] = make_pair(id, p);
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid)
    Ins(k << 1, l, mid, p, re, id);
  else
    Ins(k << 1 | 1, mid + 1, r, p, re, id);
  update(k);
}
pair<int, int> Query(int k, int l, int r, int p, int q) {
  if (l > q || r < p) return make_pair(-1, -1);
  if (l >= p && r <= q) return Max[k];
  int mid = l + r >> 1;
  return max(Query(k << 1, l, mid, p, q), Query(k << 1 | 1, mid + 1, r, p, q));
}
pair<int, int> Query1(int k, int l, int r, int p, int q) {
  if (l > q || r < p) return make_pair(N, N);
  if (l >= p && r <= q) return Min[k];
  int mid = l + r >> 1;
  return min(Query1(k << 1, l, mid, p, q),
             Query1(k << 1 | 1, mid + 1, r, p, q));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int first, second, z;
    scanf("%d%d%d", &first, &second, &z);
    E[first].push_back(second);
    W[first].push_back(z);
    E[second].push_back(first);
    W[second].push_back(z);
  }
  dfs(1, 0);
  dfs1(root, 0, 0);
  for (int i = 1; i <= n; i++) ans += dis[i];
  ans *= 2;
  cout << ans << endl;
  for (int i = E[root].size() - 1; i >= 0; i--) {
    cnt++;
    dfs2(E[root][i], root);
  }
  cnt++;
  belong[root] = cnt;
  S[cnt].insert(root);
  for (int i = 1; i <= cnt; i++) {
    sum[i] *= 2;
    Ins(1, 1, cnt, i, sum[i], *S[i].begin());
    S[i].insert(N);
  }
  for (int i = 1; i <= n; i++) {
    if (root != i) {
      pair<int, int> tmp = make_pair(-1, -1);
      if (belong[i] != 1) tmp = Query(1, 1, cnt, 1, belong[i] - 1);
      if (belong[i] != cnt)
        tmp = max(tmp, Query(1, 1, cnt, belong[i] + 1, cnt));
      if (tmp.first == n - i + 1 && tmp.second != cnt) {
        printf("%d ", *S[tmp.second].begin());
        S[tmp.second].erase(S[tmp.second].begin());
        sum[tmp.second]--;
        Ins(1, 1, cnt, tmp.second, sum[tmp.second], *S[tmp.second].begin());
      } else {
        pair<int, int> tmp = make_pair(N, N);
        if (belong[i] != 1) tmp = Query1(1, 1, cnt, 1, belong[i] - 1);
        if (belong[i] != cnt)
          tmp = min(tmp, Query1(1, 1, cnt, belong[i] + 1, cnt));
        printf("%d ", *S[tmp.second].begin());
        S[tmp.second].erase(S[tmp.second].begin());
        sum[tmp.second]--;
        Ins(1, 1, cnt, tmp.second, sum[tmp.second], *S[tmp.second].begin());
      }
      sum[belong[i]]--;
      Ins(1, 1, cnt, belong[i], sum[belong[i]], *S[belong[i]].begin());
    } else {
      pair<int, int> tmp;
      tmp = Query(1, 1, cnt, 1, cnt);
      if (tmp.first == n - i + 1 && tmp.second != cnt) {
        printf("%d ", *S[tmp.second].begin());
        S[tmp.second].erase(S[tmp.second].begin());
        sum[tmp.second]--;
        Ins(1, 1, cnt, tmp.second, sum[tmp.second], *S[tmp.second].begin());
      } else {
        pair<int, int> tmp;
        tmp = Query1(1, 1, cnt, 1, cnt);
        printf("%d ", *S[tmp.second].begin());
        S[tmp.second].erase(S[tmp.second].begin());
        sum[tmp.second]--;
        Ins(1, 1, cnt, tmp.second, sum[tmp.second], *S[tmp.second].begin());
      }
    }
  }
}
