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 MAXN = 100005;
struct segment_tree {
  int v[MAXN << 2];
  void build(int l, int r, int rt) {
    if (l == r) {
      v[rt] = l;
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    v[rt] = min(v[rt << 1], v[rt << 1 | 1]);
  }
  void update(int pos, int val, int l, int r, int rt) {
    if (l == r) {
      v[rt] = val;
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(pos, val, l, mid, rt << 1);
    if (pos > mid) update(pos, val, mid + 1, r, rt << 1 | 1);
    v[rt] = min(v[rt << 1], v[rt << 1 | 1]);
  }
  int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
      return v[rt];
    }
    int mid = (l + r) >> 1;
    if (R <= mid) return query(L, R, l, mid, rt << 1);
    if (L > mid) return query(L, R, mid + 1, r, rt << 1 | 1);
    return min(query(L, R, l, mid, rt << 1),
               query(L, R, mid + 1, r, rt << 1 | 1));
  }
};
segment_tree tree;
int n;
vector<int> e[MAXN], d[MAXN];
int size[MAXN];
void cal_size(int u, int fu) {
  size[u] = 1;
  int sz = (int)e[u].size();
  for (int i = 0; i < sz; ++i) {
    int v = e[u][i];
    if (v == fu) continue;
    cal_size(v, u);
    size[u] += size[v];
  }
}
int max_subtree_size, tree_centre;
void cal_centre(int u, int fu, int all) {
  int val = 0;
  int sz = (int)e[u].size();
  for (int i = 0; i < sz; ++i) {
    int v = e[u][i];
    if (v == fu) continue;
    cal_centre(v, u, all);
    val = max(val, size[v]);
  }
  val = max(val, all - size[u]);
  if (val < max_subtree_size) {
    max_subtree_size = val;
    tree_centre = u;
  }
}
void get_tree_centre(int u) {
  cal_size(u, 0);
  max_subtree_size = size[u], tree_centre = u;
  cal_centre(u, 0, size[u]);
}
long long ans = 0;
void get_ans(int u, int fu, long long dis) {
  ans += dis;
  int sz = (int)e[u].size();
  for (int i = 0; i < sz; ++i) {
    int v = e[u][i];
    if (v == fu) continue;
    get_ans(v, u, dis + d[u][i]);
  }
}
int belong[MAXN], l[MAXN], r[MAXN], tot, p[MAXN];
void dfs(int u, int fu, int group) {
  size[u] = 1;
  belong[u] = group;
  l[u] = ++tot;
  int sz = (int)e[u].size();
  for (int i = 0; i < sz; ++i) {
    int v = e[u][i];
    if (v == fu) continue;
    dfs(v, u, group);
    size[u] += size[v];
  }
  r[u] = tot;
}
set<int> s[MAXN];
vector<int> t;
int solve(int u, int op) {
  if (op == 0) {
    if (r[u] == n) return tree.query(1, l[u] - 1, 1, n, 1);
    return min(tree.query(1, l[u] - 1, 1, n, 1),
               tree.query(r[u] + 1, n, 1, n, 1));
  }
  return tree.query(l[u], r[u], 1, n, 1);
}
int MAIN() {
  scanf("%d", &n);
  int u, v, w;
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    e[u].push_back(v), e[v].push_back(u);
    d[u].push_back(w), d[v].push_back(w);
  }
  get_tree_centre(1);
  u = tree_centre;
  get_ans(u, 0, 0);
  printf("%lld\n", ans * 2);
  int sz = (int)e[u].size();
  l[u] = r[u] = 1, belong[u] = u;
  tot = 1;
  for (int i = 0; i < sz; ++i) {
    int v = e[u][i];
    dfs(v, u, v);
    size[v] *= 2;
    s[size[v]].insert(v);
  }
  for (int i = 1; i <= n; ++i) {
    tree.update(l[i], i, 1, n, 1);
  }
  for (int i = 1; i <= n; ++i) {
    t.clear();
    for (set<int>::iterator it = s[n + 1 - i].begin(); it != s[n + 1 - i].end();
         it++) {
      t.push_back(*it);
    }
    if (t.size() == 2) {
      if (belong[i] == t[0]) {
        p[i] = solve(t[1], 1);
      } else {
        p[i] = solve(t[0], 1);
      }
    } else if (t.size() == 1) {
      if (belong[i] == t[0]) {
        p[i] = solve(t[0], 0);
      } else {
        p[i] = solve(t[0], 1);
      }
    } else {
      if (i == tree_centre) {
        p[i] = tree.v[1];
      } else {
        p[i] = solve(belong[i], 0);
      }
    }
    tree.update(l[p[i]], MAXN << 2, 1, n, 1);
    int a = belong[i], b = belong[p[i]];
    if (a != tree_centre) s[size[a]].erase(a), s[--size[a]].insert(a);
    if (b != tree_centre) s[size[b]].erase(b), s[--size[b]].insert(b);
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d%c", p[i], i < n ? ' ' : '\n');
  }
  return 0;
}
int main() {
  ios ::sync_with_stdio(false);
  cout << fixed << setprecision(16);
  return MAIN();
}
