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 = 100005;
struct edge {
  int to, next, v;
} e[N * 2];
int head[N], n, tot;
int sz[N], mxv, rt;
int co[N], sz1[N], sz2[N], mat[N];
set<int> S[N];
set<pair<int, int> > SS, SSS;
long long ans;
void add(int x, int y, int v) {
  e[++tot] = (edge){y, head[x], v};
  head[x] = tot;
}
void dfs(int x, int fa) {
  sz[x] = 1;
  int mx = 0;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa) {
      dfs(e[i].to, x);
      sz[x] += sz[e[i].to];
      mx = max(mx, sz[e[i].to]);
      ans += 2ll * min(sz[e[i].to], n - sz[e[i].to]) * e[i].v;
    }
  mx = max(mx, n - sz[x]);
  if (mx < mxv) mxv = mx, rt = x;
}
void color(int x, int fa, int c) {
  co[x] = c;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa) color(e[i].to, x, c);
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n - 1); i++) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    add(x, y, v);
    add(y, x, v);
  }
  mxv = 1 << 30;
  dfs(1, 0);
  printf("%lld\n", ans);
  co[rt] = rt;
  for (int i = head[rt]; i; i = e[i].next) color(e[i].to, rt, e[i].to);
  for (int i = (int)(1); i <= (int)(n); i++) S[co[i]].insert(i);
  for (int i = (int)(1); i <= (int)(n); i++) S[i].insert(1 << 30);
  for (int i = (int)(1); i <= (int)(n); i++) ++sz1[co[i]], ++sz2[co[i]];
  --sz2[rt];
  for (int i = (int)(1); i <= (int)(n); i++)
    if (co[i] == i) SS.insert(pair<int, int>(*S[i].begin(), i));
  for (int i = (int)(1); i <= (int)(n); i++)
    if (co[i] == i) SSS.insert(pair<int, int>(sz1[i] + sz2[i], i));
  for (int i = (int)(1); i <= (int)(n); i++) {
    int be = co[i];
    SSS.erase(pair<int, int>(sz1[be] + sz2[be], be));
    --sz1[be];
    SSS.insert(pair<int, int>(sz1[be] + sz2[be], be));
    int id;
    if (SSS.rbegin()->first == n - i + 1)
      id = SSS.rbegin()->second;
    else {
      set<pair<int, int> >::iterator it = SS.begin();
      if (it->second == be && i != rt) ++it;
      id = it->second;
    }
    mat[i] = *S[id].begin();
    SS.erase(pair<int, int>(*S[id].begin(), id));
    S[id].erase(S[id].begin());
    SS.insert(pair<int, int>(*S[id].begin(), id));
    SSS.erase(pair<int, int>(sz1[id] + sz2[id], id));
    --sz2[id];
    SSS.insert(pair<int, int>(sz1[id] + sz2[id], id));
  }
  for (int i = (int)(1); i <= (int)(n); i++) printf("%d ", mat[i]);
  puts("");
}
