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 LL = long long;
const int N = 100000 + 5;
const int INF = 0x3f3f3f3f;
int n, st[N], ed[N], size[N], match[N], tim, belong[N];
LL dis[N];
int parent[N], que[N];
struct Edge {
  int v, w;
  Edge(int v = 0, int w = 0) : v(v), w(w) {}
};
std::vector<Edge> edges[N];
struct SegmentTree {
  int t[N << 2];
  void modify(int p, int v, int l = 0, int r = n, int rt = 1) {
    if (l == r) {
      t[rt] = v;
      return;
    }
    int mid = l + r >> 1;
    if (p <= mid)
      modify(p, v, l, mid, rt << 1);
    else
      modify(p, v, mid + 1, r, rt << 1 | 1);
    t[rt] = std::min(t[rt << 1], t[rt << 1 | 1]);
  }
  int query(int L, int R, int l = 0, int r = n, int rt = 1) {
    if (L <= l && r <= R) {
      return t[rt];
    }
    int mid = l + r >> 1;
    if (L <= mid && mid < R)
      return std::min(query(L, R, l, mid, rt << 1),
                      query(L, R, mid + 1, r, rt << 1 | 1));
    else if (L <= mid)
      return query(L, R, l, mid, rt << 1);
    else
      return query(L, R, mid + 1, r, rt << 1 | 1);
  }
} sgt;
int get_root() {
  int qf = 0, qe = 0;
  que[qe++] = 0;
  parent[0] = -1;
  while (qf != qe) {
    int u = que[qf++];
    for (Edge e : edges[u]) {
      if (e.v == parent[u]) continue;
      que[qe++] = e.v;
      parent[e.v] = u;
    }
  }
  int root = -1, vmin = INF;
  for (int I = qe - 1; I >= 0; --I) {
    int u = que[I];
    size[u] = 1;
    int mx = -1;
    for (Edge e : edges[u]) {
      if (e.v == parent[u]) continue;
      mx = std::max(mx, size[e.v]);
      size[u] += size[e.v];
    }
    mx = std::max(mx, n - size[u]);
    if (vmin > mx) {
      vmin = mx;
      root = u;
    }
  }
  return root;
}
void dfs(int u, int fa, int key) {
  st[u] = ++tim;
  belong[u] = key;
  size[u] = 1;
  for (Edge e : edges[u]) {
    if (e.v == fa) continue;
    dis[e.v] = dis[u] + e.w;
    dfs(e.v, u, key);
    size[u] += size[e.v];
  }
  ed[u] = tim;
}
void solve() {
  int root = get_root();
  for (Edge e : edges[root]) {
    dis[e.v] = e.w;
    dfs(e.v, root, e.v);
  }
  st[root] = ed[root] = ++tim;
  belong[root] = root;
  for (int i = 0; i < n; ++i) {
    sgt.modify(st[i], i);
  }
  std::set<std::pair<int, int>> set;
  for (Edge e : edges[root]) {
    size[e.v] <<= 1;
    set.insert(std::make_pair(size[e.v], e.v));
  }
  size[root] = 2;
  set.insert(std::make_pair(size[root], root));
  memset(match, -1, sizeof(match));
  std::set<std::pair<int, int>>::iterator it;
  for (int i = 0; i < n; ++i) {
    int left = n - i;
    int t = belong[i];
    set.erase(std::make_pair(size[t], t));
    int v = INF;
    if (!set.empty()) {
      it = --set.end();
      if (it->second != root && it->first > left - 1) {
        v = sgt.query(st[it->second], ed[it->second]);
      } else {
        if (1 < st[t]) {
          v = std::min(v, sgt.query(1, st[t] - 1));
        }
        if (ed[t] < tim) {
          v = std::min(v, sgt.query(ed[t] + 1, tim));
        }
        v = std::min(v, sgt.query(st[root], ed[root]));
      }
    } else {
      v = std::min(v, sgt.query(st[root], ed[root]));
    }
    match[i] = v;
    sgt.modify(st[v], INF);
    int s = belong[v];
    if (--size[t]) {
      set.insert(std::make_pair(size[t], t));
    }
    set.erase(std::make_pair(size[s], s));
    if (--size[s]) {
      set.insert(std::make_pair(size[s], s));
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    edges[a].push_back(Edge(b, c));
    edges[b].push_back(Edge(a, c));
  }
  solve();
  LL answer = 0;
  for (int i = 0; i < n; ++i) answer += dis[i];
  printf("%I64d\n", answer << 1);
  for (int i = 0; i < n; ++i) {
    printf("%d%c", match[i] + 1, " \n"[i == n]);
  }
  return 0;
}
