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 data {
  int nex, to, w;
} e[100010 * 2];
int head[100010], edge = 0, size[100010], deep[100010], f[100010], dfn[100010],
                  dfp[100010], ed[100010], g[100010], top[100010], rt, n,
                  de = 0, bl = 0;
int c1[100010], c2[100010];
set<pair<int, int> > st;
namespace segtree {
int b[100010 * 4];
void build(int o, int l, int r) {
  if (l == r) {
    b[o] = dfp[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(o * 2, l, mid), build(o * 2 + 1, mid + 1, r);
  b[o] = min(b[o * 2], b[o * 2 + 1]);
}
void change(int o, int l, int r, int p) {
  if (l == r) {
    b[o] = 2000000000;
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    change(o * 2, l, mid, p);
  else
    change(o * 2 + 1, mid + 1, r, p);
  b[o] = min(b[o * 2], b[o * 2 + 1]);
}
int query(int o, int l, int r, int u, int v) {
  if (l > v || r < u || u > v) return 2000000000;
  if (l >= u && r <= v) return b[o];
  int mid = (l + r) >> 1;
  if (v <= mid)
    return query(o * 2, l, mid, u, v);
  else if (u > mid)
    return query(o * 2 + 1, mid + 1, r, u, v);
  else
    return min(query(o * 2, l, mid, u, mid),
               query(o * 2 + 1, mid + 1, r, mid + 1, v));
}
};  // namespace segtree
inline void add(int from, int to, int w) {
  e[++edge].nex = head[from];
  e[edge].to = to;
  e[edge].w = w;
  head[from] = edge;
}
void getrt(int x, int fa) {
  f[x] = 0;
  size[x] = 1;
  for (int i = head[x]; i; i = e[i].nex) {
    int v = e[i].to;
    if (v == fa) continue;
    getrt(v, x);
    size[x] += size[v];
    f[x] = max(f[x], size[v]);
  }
  f[x] = max(f[x], n - size[x]);
  if (f[x] < f[rt]) rt = x;
}
void dfs(int x, int fa) {
  size[x] = 1;
  dfn[x] = ++de, dfp[de] = x;
  if (fa == rt)
    top[x] = x;
  else
    top[x] = top[fa];
  for (int i = head[x]; i; i = e[i].nex) {
    int v = e[i].to;
    if (v == fa) continue;
    deep[v] = deep[x] + 1;
    dfs(v, x);
    size[x] += size[v];
  }
  ed[x] = de;
}
int main() {
  int x, y, z;
  scanf("%d", &n);
  for (register int i = 1; i < n; i++)
    scanf("%d%d%d", &x, &y, &z), add(x, y, z), add(y, x, z);
  if (n == 1) printf("0\n1"), exit(0);
  rt = 0, f[0] = 2000000000;
  getrt(1, 0);
  memset(size, 0, sizeof(size));
  deep[1] = 1;
  dfs(rt, 0);
  register long long ans = 0;
  for (register int i = 1; i <= edge; i += 2) {
    int u = e[i].to, v = e[i + 1].to;
    if (deep[u] > deep[v]) swap(u, v);
    ans += (long long)min(size[v], n - size[v]) * 2 * e[i].w;
  }
  segtree::build(1, 1, n);
  for (int i = head[rt]; i; i = e[i].nex)
    st.insert(make_pair(size[e[i].to] * 2, e[i].to)),
        c1[e[i].to] = c2[e[i].to] = size[e[i].to];
  for (register int i = 1; i <= n; i++) {
    if ((--st.end())->first == n - i + 1) {
      pair<int, int> u = *--st.end();
      if (u.second != top[i]) {
        st.erase(u);
        g[i] = segtree::query(1, 1, n, dfn[u.second], ed[u.second]);
        c2[u.second]--;
        st.insert(make_pair(u.first - 1, u.second));
        register int k = top[i];
        if (k) {
          st.erase(make_pair(c1[k] + c2[k], k));
          c1[k]--;
          st.insert(make_pair(c1[k] + c2[k], k));
        }
        segtree::change(1, 1, n, dfn[g[i]]);
        continue;
      }
    }
    g[i] = min(segtree::query(1, 1, n, 1, dfn[top[i]] - 1),
               segtree::query(1, 1, n, ed[top[i]] + 1, n));
    register int k = top[i];
    if (k) {
      st.erase(make_pair(c1[k] + c2[k], k));
      c1[k]--;
      st.insert(make_pair(c1[k] + c2[k], k));
    }
    k = top[g[i]];
    if (k) {
      st.erase(make_pair(c1[k] + c2[k], k));
      c2[k]--;
      st.insert(make_pair(c1[k] + c2[k], k));
    }
    segtree::change(1, 1, n, dfn[g[i]]);
  }
  printf("%I64d\n", ans);
  for (int i = 1; i <= n; i++) printf("%d ", g[i]);
  return 0;
}
