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 N = 100005, INF = 0x3f3f3f3f;
int n, ans[N];
long long sum;
vector<int> V[N];
vector<int> W[N];
void add(int u, int v, int w) {
  V[u].push_back(v);
  W[u].push_back(w);
}
int rt, rtt, sz[N], mx, num[N];
int maximize(int& a, int b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int minimize(int& a, int b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
void getRoot(int u, int fa = 0) {
  num[u] = 0;
  sz[u] = 1;
  for (int i = 0; i < V[u].size(); ++i) {
    int v = V[u][i];
    if (v == fa) continue;
    getRoot(v, u);
    maximize(num[u], sz[v]);
    sz[u] += sz[v];
  }
  maximize(num[u], n - sz[u]);
  if (minimize(mx, num[u])) rt = u;
}
int check() {
  for (int i = 0; i < V[rt].size(); ++i) {
    int v = V[rt][i];
    if (num[v] == mx) return rtt = v;
  }
  return 0;
}
int A[N], B[N], tot, belong[N];
int L[N], R[N], val[N << 2];
void dfs2(int u, int fa, int* A, int t) {
  belong[u] = t;
  A[tot++] = u;
  for (int i = 0; i < V[u].size(); ++i) {
    int v = V[u][i];
    if (v == fa) continue;
    dfs2(v, u, A, t);
  }
}
void dfs1(int u, int k, int fa) {
  belong[u] = k;
  B[u] = tot;
  A[tot++] = u;
  for (int i = 0; i < V[u].size(); ++i) {
    int v = V[u][i];
    if (v == fa) continue;
    dfs1(v, k, u);
  }
}
void push_up(int rt) { val[rt] = min(val[rt << 1], val[rt << 1 | 1]); }
void build(int l = 1, int r = n - 1, int rt = 1) {
  if (l == r) {
    val[rt] = A[l];
    return;
  }
  int m = l + r >> 1;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  push_up(rt);
}
void update(int p, int l = 1, int r = n - 1, int rt = 1) {
  if (l == r) {
    val[rt] = INF;
    return;
  }
  int m = l + r >> 1;
  if (p <= m)
    update(p, l, m, rt << 1);
  else
    update(p, m + 1, r, rt << 1 | 1);
  push_up(rt);
}
int query(int L, int R, int l = 1, int r = n - 1, int rt = 1) {
  if (L <= l && r <= R) {
    return val[rt];
  }
  int m = l + r >> 1;
  int ret = INF;
  if (L <= m) minimize(ret, query(L, R, l, m, rt << 1));
  if (R > m) minimize(ret, query(L, R, m + 1, r, rt << 1 | 1));
  return ret;
}
void getAns(int u, int fa = 0, long long d = 0) {
  sum += d;
  for (int i = 0; i < V[u].size(); ++i) {
    int v = V[u][i], w = W[u][i];
    if (v == fa) continue;
    getAns(v, u, d + w);
  }
}
struct Node {
  int val, id;
  Node(int val = 0, int id = 0) : val(val), id(id) {}
  bool operator<(const Node& x) const {
    if (val == x.val) return id < x.id;
    return val > x.val;
  }
};
set<Node> S;
int P[N], flg, cnt;
void Upd(int t) {
  if (t == rt) return;
  S.erase(Node(P[belong[t]], belong[t]));
  S.insert(Node(--P[belong[t]], belong[t]));
}
int main() {
  scanf("%d", &n);
  if (n == 1) {
    printf("0\n1\n");
    return 0;
  }
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
    add(v, u, w);
  }
  mx = INF;
  getRoot(1);
  getAns(rt);
  if (check()) {
    tot = 0;
    dfs2(rt, rtt, A, 0);
    tot = 0;
    dfs2(rtt, rt, B, 1);
    sort(A, A + n / 2);
    sort(B, B + n / 2);
    int ta = 0, tb = 0;
    for (int i = 1; i <= n; ++i) {
      if (belong[i]) {
        ans[i] = A[ta++];
      } else {
        ans[i] = B[tb++];
      }
    }
  } else {
    tot = 1;
    for (int i = 0; i < V[rt].size(); ++i) {
      L[i] = tot;
      dfs1(V[rt][i], i, rt);
      R[i] = tot - 1;
      P[i] = 2 * (R[i] - L[i] + 1);
      S.insert(Node(P[i], i));
    }
    build();
    cnt = n;
    flg = 1;
    for (int i = 1; i <= n; ++i) {
      Node now = *S.begin();
      int t = INF;
      if (now.val == cnt && (i == rt || belong[i] != now.id)) {
        minimize(t, query(L[now.id], R[now.id]));
      } else if (i == rt) {
        t = val[1];
        if (flg) minimize(t, rt);
      } else {
        if (1 <= L[belong[i]] - 1) minimize(t, query(1, L[belong[i]] - 1));
        if (R[belong[i]] + 1 <= n - 1)
          minimize(t, query(R[belong[i]] + 1, n - 1));
        if (flg) minimize(t, rt);
      }
      if (t == rt)
        flg = 0;
      else
        update(B[t]);
      Upd(i);
      Upd(t);
      --cnt;
      ans[i] = t;
    }
  }
  printf("%I64d\n", sum << 1);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}
