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 edge {
  int to, next, val;
} e[100005 << 1];
int h[100005], tp = 1;
void ae(int u, int v, int w) {
  e[++tp].to = v;
  e[tp].next = h[u];
  e[tp].val = w;
  h[u] = tp;
}
int siz[100005], mx[100005], n;
int mn[100005 << 2], st[100005], ed[100005], rk[100005], top[100005], tim;
int lsiz[100005], rsiz[100005];
long long dis[100005];
int p[100005];
void dfsroot(int u, int f, int &rt) {
  siz[u] = 1;
  for (int v, i = h[u]; i; i = e[i].next)
    if ((v = e[i].to) != f) {
      dfsroot(v, u, rt);
      siz[u] += siz[v];
      mx[u] = max(mx[u], siz[v]);
    }
  mx[u] = max(mx[u], n - siz[u]);
  if (!rt || mx[rt] > mx[u]) rt = u;
}
void dfs(int u, int f, int tp) {
  lsiz[tp]++;
  rsiz[tp]++;
  st[u] = ++tim;
  rk[tim] = u;
  top[u] = tp;
  for (int i = h[u]; i; i = e[i].next)
    if (e[i].to != f) {
      dis[e[i].to] = dis[u] + e[i].val;
      dfs(e[i].to, u, tp);
    }
  ed[u] = tim;
}
void build(int l, int r, int rt) {
  if (l == r) {
    mn[rt] = rk[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
}
int find(int l, int r, int rt, int L, int R) {
  if (R < L) return n + 1;
  if (L == l && R == r) return mn[rt];
  int mid = (l + r) >> 1;
  if (R <= mid)
    return find(l, mid, rt << 1, L, R);
  else if (L > mid)
    return find(mid + 1, r, rt << 1 | 1, L, R);
  else
    return min(find(l, mid, rt << 1, L, mid),
               find(mid + 1, r, rt << 1 | 1, mid + 1, R));
}
void update(int l, int r, int rt, int p) {
  if (l == r) {
    mn[rt] = n + 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    update(l, mid, rt << 1, p);
  else
    update(mid + 1, r, rt << 1 | 1, p);
  mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
}
struct node {
  int x;
  bool operator<(const node &a) const {
    if (lsiz[x] + rsiz[x] == lsiz[a.x] + rsiz[a.x]) return x < a.x;
    return lsiz[x] + rsiz[x] > lsiz[a.x] + rsiz[a.x];
  }
  node(int a = 0) : x(a) {}
};
set<node> s;
int main() {
  cin >> n;
  for (int u, v, w, i = 1; i < n; i++) {
    scanf("%d%d%d", &u, &v, &w);
    ae(u, v, w);
    ae(v, u, w);
  }
  int rt = 0;
  dfsroot(1, 0, rt);
  st[rt] = tim = 1;
  ed[rt] = n;
  rk[1] = rt;
  for (int i = h[rt]; i; i = e[i].next) {
    dis[e[i].to] = e[i].val;
    dfs(e[i].to, rt, e[i].to);
  }
  build(1, n, 1);
  long long ans = 0;
  for (int i = h[rt]; i; i = e[i].next) s.insert(node(e[i].to));
  for (int i = 1; i <= n; i++) {
    s.erase(node(top[i]));
    lsiz[top[i]]--;
    s.insert(node(top[i]));
    int u = (*s.begin()).x;
    if (lsiz[u] + rsiz[u] >= n - i + 1)
      p[i] = find(1, n, 1, st[u], ed[u]);
    else
      p[i] = min(find(1, n, 1, 1, st[top[i]] - 1),
                 find(1, n, 1, ed[top[i]] + 1, n));
    s.erase(node(top[p[i]]));
    rsiz[top[p[i]]]--;
    s.insert(node(top[p[i]]));
    ans += 2 * dis[i];
    update(1, n, 1, st[p[i]]);
  }
  printf("%I64d\n", ans);
  for (int i = 1; i <= n; i++) printf("%d ", p[i]);
}
