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 = 100000 + 10, inf = 1e9;
struct Edge {
  int v, w, nxt;
  Edge() {}
  Edge(int _v, int _w, int _n) : v(_v), w(_w), nxt(_n) {}
} E[MAXN << 1];
int G[MAXN], size[MAXN];
long long dis[MAXN];
int st[MAXN], ed[MAXN], belong[MAXN];
int n, sz, root, mins;
void getroot(int u, int f = -1) {
  size[u] = 1;
  int mx = 0;
  for (int now = G[u]; ~now; now = E[now].nxt) {
    int v = E[now].v;
    if (v == f) continue;
    getroot(v, u);
    size[u] += size[v];
    mx = max(mx, size[v]);
  }
  mx = max(mx, n - size[u]);
  if (mx < mins || (mx == mins && u < root)) root = u, mins = mx;
}
void dfs(int u, int f, int subtree) {
  size[u] = 1;
  belong[u] = subtree;
  st[u] = sz++;
  for (int now = G[u]; ~now; now = E[now].nxt) {
    int v = E[now].v, w = E[now].w;
    if (v == f) continue;
    dis[v] = dis[u] + w;
    dfs(v, u, subtree);
    size[u] += size[v];
  }
  ed[u] = sz;
}
namespace SegTree {
int mx[MAXN << 2];
void modify(int rt, int l, int r, int p, int v) {
  if (l + 1 == r) {
    mx[rt] = v;
    return;
  }
  if (p < ((l + r) >> 1))
    modify((rt << 1), l, ((l + r) >> 1), p, v);
  else
    modify((rt << 1 | 1), ((l + r) >> 1), r, p, v);
  mx[rt] = min(mx[(rt << 1)], mx[(rt << 1 | 1)]);
}
int query(int rt, int l, int r, int L, int R) {
  if (L <= l && R >= r) return mx[rt];
  int ret = inf;
  if (L < ((l + r) >> 1))
    ret = min(ret, query((rt << 1), l, ((l + r) >> 1), L, R));
  if (R > ((l + r) >> 1))
    ret = min(ret, query((rt << 1 | 1), ((l + r) >> 1), r, L, R));
  return ret;
}
}  // namespace SegTree
set<pair<int, int> > S;
int match[MAXN];
void solve() {
  mins = inf;
  getroot(0);
  sz = 0;
  belong[root] = root;
  dis[root] = 0;
  for (int now = G[root]; ~now; now = E[now].nxt) {
    int v = E[now].v, w = E[now].w;
    dis[v] = w;
    dfs(v, root, v);
    S.insert(pair<int, int>(size[v] <<= 1, v));
  }
  st[root] = sz++;
  ed[root] = sz;
  size[root] = 2;
  S.insert(pair<int, int>(size[root], root));
  long long ret = 0;
  for (int i = 0; i < n; ++i) {
    SegTree::modify(1, 0, n, st[i], i);
    ret += dis[i];
  }
  for (int i = 0; i < n; ++i) {
    int unmatch = n - i, anc = belong[i], pt = inf;
    S.erase(pair<int, int>(size[anc], anc));
    if (!S.empty()) {
      auto it = S.rbegin();
      if (it->second != root && it->first > unmatch - 1) {
        pt = SegTree::query(1, 0, n, st[it->second], ed[it->second]);
      } else {
        if (ed[anc] < sz) pt = SegTree::query(1, 0, n, ed[anc], sz);
        if (st[anc] > 0) pt = min(pt, SegTree::query(1, 0, n, 0, st[anc]));
        pt = min(pt, SegTree::query(1, 0, n, st[root], ed[root]));
      }
    } else
      pt = SegTree::query(1, 0, n, st[root], ed[root]);
    match[i] = pt;
    SegTree::modify(1, 0, n, st[pt], inf);
    if (--size[anc]) S.insert(pair<int, int>(size[anc], anc));
    anc = belong[pt];
    S.erase(pair<int, int>(size[anc], anc));
    if (--size[anc]) S.insert(pair<int, int>(size[anc], anc));
  }
  printf("%lld\n", ret << 1);
  for (int i = 0; i < n; ++i) {
    printf("%d%c", match[i] + 1, " \n"[i == n - 1]);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; ++i) G[i] = -1;
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    E[sz] = Edge(v, w, G[u]);
    G[u] = sz++;
    E[sz] = Edge(u, w, G[v]);
    G[v] = sz++;
  }
  solve();
  return 0;
}
