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;
int n;
struct Edge {
  int to;
  int val;
  int next;
} edge[100005 << 1];
int head[100005];
int cnt;
void Addedge(int fr, int to, int val) {
  edge[++cnt].to = to;
  edge[cnt].val = val;
  edge[cnt].next = head[fr];
  head[fr] = cnt;
}
int root;
int size[100005];
int DFS1(int now, int last) {
  size[now] = 1;
  bool flag = 1;
  for (int tmp, i = head[now]; i; i = edge[i].next)
    if (edge[i].to ^ last) {
      tmp = DFS1(edge[i].to, now);
      if (tmp) return tmp;
      if (size[edge[i].to] << 1 > n) flag = 0;
      size[now] += size[edge[i].to];
    }
  if (n - size[now] << 1 > n) flag = 0;
  return flag ? now : 0;
}
int tr[100005 << 2];
void Pushup(int rt) { tr[rt] = min(tr[rt << 1], tr[rt << 1 | 1]); }
void Update(int pos, int val, int l, int r, int rt) {
  if (l == r) {
    tr[rt] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    Update(pos, val, l, mid, rt << 1);
  else
    Update(pos, val, mid + 1, r, rt << 1 | 1);
  Pushup(rt);
}
int Query(int L, int R, int l, int r, int rt) {
  if (L > R) return 0x3f3f3f3f;
  if (L <= l && r <= R) return tr[rt];
  int mid = (l + r) >> 1;
  if (R <= mid)
    return Query(L, R, l, mid, rt << 1);
  else if (mid < L)
    return Query(L, R, mid + 1, r, rt << 1 | 1);
  else
    return min(Query(L, R, l, mid, rt << 1),
               Query(L, R, mid + 1, r, rt << 1 | 1));
}
long long dis[100005], ans;
int st[100005], en[100005], dep;
int bel[100005];
void DFS2(int now, int last, int belong) {
  ans += dis[now];
  bel[now] = belong;
  st[now] = ++dep;
  Update(st[now], now, 1, n, 1);
  size[now] = 1;
  for (int i = head[now]; i; i = edge[i].next)
    if (edge[i].to ^ last) {
      dis[edge[i].to] = dis[now] + edge[i].val;
      DFS2(edge[i].to, now, last ? belong : edge[i].to);
      size[now] += size[edge[i].to];
    }
  en[now] = dep;
}
set<pair<int, int> > Set;
int sum[100005];
int p[100005];
int main() {
  scanf("%d", &n);
  for (int u, v, w, i = 2; i <= n; i++) {
    scanf("%d%d%d", &u, &v, &w);
    Addedge(u, v, w);
    Addedge(v, u, w);
  }
  root = DFS1(1, 0);
  DFS2(root, 0, root);
  en[root] = 1;
  printf("%I64d\n", ans << 1);
  sum[root] = 2;
  for (int i = head[root]; i; i = edge[i].next) {
    sum[edge[i].to] = size[edge[i].to] << 1;
    Set.insert(make_pair(sum[edge[i].to], edge[i].to));
  }
  set<pair<int, int> >::iterator it;
  for (int which, i = 1; i <= n; i++) {
    Set.erase(make_pair(sum[bel[i]], bel[i]));
    sum[bel[i]]--;
    Set.insert(make_pair(sum[bel[i]], bel[i]));
    it = Set.lower_bound(make_pair(n - i + 1, 0));
    if (it != Set.end() && it->first == n - i + 1)
      which = Query(st[it->second], en[it->second], 1, n, 1);
    else if (i ^ root)
      which = min(Query(1, st[bel[i]] - 1, 1, n, 1),
                  Query(en[bel[i]] + 1, n, 1, n, 1));
    else
      which = Query(1, n, 1, n, 1);
    p[i] = which;
    Update(st[which], 0x3f3f3f3f, 1, n, 1);
    Set.erase(make_pair(sum[bel[which]], bel[which]));
    sum[bel[which]]--;
    Set.insert(make_pair(sum[bel[which]], bel[which]));
  }
  for (int i = 1; i <= n; i++) printf("%d%c", p[i], i ^ n ? ' ' : '\n');
  return 0;
}
