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;
struct ob {
  long long x, id;
  bool operator<(const ob& y) const { return x < y.x; }
} h;
struct edge {
  long long x, w;
};
long long siz[100005], dp[100005], u1[100005],
    cnt = 0, f, u2[100005], tot1 = 0, tot2 = 0, x, tr, y, w, n, i, p[100005],
    dsu[100005], a[100005], b[100005], ans = 0, r;
vector<edge> s[100005];
set<int> sz, st[100005];
set<int>::iterator it;
priority_queue<ob> q;
void dfs2(int p, int v, int f) {
  long long i;
  edge vp;
  a[v]++;
  b[v]++;
  dsu[p] = v;
  st[v].insert(p);
  for (i = 0; i < s[p].size(); i++) {
    vp = s[p][i];
    if (vp.x == f) continue;
    dfs2(vp.x, v, p);
  }
}
void dfs(int p, int f) {
  long long i;
  edge v;
  siz[p] = 1;
  for (i = 0; i < s[p].size(); i++) {
    v = s[p][i];
    if (v.x == f) continue;
    dfs(v.x, p);
    ans += 2LL * min(siz[v.x], n - siz[v.x]) * v.w;
    siz[p] += siz[v.x];
    dp[p] = max(dp[p], siz[v.x]);
  }
  dp[p] = max(dp[p], n - siz[p]);
}
void dfsu(int p, int f) {
  long long i;
  edge v;
  dsu[p] = 1;
  for (i = 0; i < s[p].size(); i++) {
    v = s[p][i];
    if (dp[v.x] == n / 2 || v.x == f) continue;
    dfsu(v.x, p);
  }
}
int main() {
  scanf("%lld", &n);
  for (i = 1; i < n; i++) {
    scanf("%lld%lld%lld", &x, &y, &w);
    s[x].push_back((edge){y, w});
    s[y].push_back((edge){x, w});
  }
  dfs(1, 0);
  r = 0;
  dp[0] = 1e18;
  printf("%lld\n", ans);
  for (i = 1; i <= n; i++)
    if (dp[i] < dp[r]) r = i;
  if (dp[r] == n / 2 && n % 2 == 0) {
    dfsu(r, 0);
    for (i = 1; i <= n; i++) {
      if (dsu[i] == 0)
        u1[++tot1] = i;
      else
        u2[++tot2] = i;
    }
    tot1 = tot2 = 0;
    for (i = 1; i <= n; i++) {
      if (dsu[i] == 0)
        printf("%lld ", u2[++tot2]);
      else
        printf("%lld ", u1[++tot1]);
    }
  } else {
    for (i = 0; i < s[r].size(); i++)
      cnt++, dfs2(s[r][i].x, cnt, r), sz.insert((*st[cnt].begin())),
          q.push((ob){a[cnt] + b[cnt], cnt});
    sz.insert(r);
    for (i = 1; i <= n; i++) {
      while (!q.empty() && (h = q.top()).x != a[h.id] + b[h.id]) q.pop();
      if (dsu[i] != h.id && h.x > n - i) {
        printf("%lld ", f = (*st[h.id].begin()));
      } else {
        if (i == r)
          printf("%lld ", f = (*sz.begin()));
        else {
          it = sz.begin();
          if (dsu[(*it)] == dsu[i])
            printf("%lld ", f = (*(++it)));
          else
            printf("%lld ", f = (*it));
        }
      }
      a[dsu[i]]--;
      b[dsu[f]]--;
      if (dsu[i]) q.push((ob){a[dsu[i]] + b[dsu[i]], dsu[i]});
      if (dsu[f]) q.push((ob){a[dsu[f]] + b[dsu[f]], dsu[f]});
      sz.erase(f);
      if (dsu[f]) {
        st[dsu[f]].erase(f);
        if (st[dsu[f]].size() > 0) sz.insert((*st[dsu[f]].begin()));
      }
    }
  }
  return 0;
}
