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;
void Read(int &p) {
  p = 0;
  char c = getchar();
  for (; c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) p = p * 10 + c - '0';
}
struct Node {
  int x, y;
  Node() { x = y = 0; }
  Node(int a, int b) { x = a, y = b; }
};
bool operator<(Node a, Node b) { return a.x < b.x; }
priority_queue<Node> q[100005], Q, que;
int n, m, x, y, z, rot, mi = 1e9, si[100005], nm = 0, be[100005];
int fir[100005], tar[200005], len[200005], nex[200005], cnt;
long long ans1;
void Add(int a, int b, int c) {
  ++cnt;
  tar[cnt] = b;
  len[cnt] = c;
  nex[cnt] = fir[a];
  fir[a] = cnt;
}
int Dfs(int r, int fa) {
  int sz = 1, mx = 0;
  for (int i = fir[r]; i; i = nex[i]) {
    int v = tar[i];
    if (v != fa) {
      int sum = Dfs(v, r);
      mx = max(mx, sum);
      sz += sum;
      ans1 += (long long)len[i] * min(sum, n - sum);
    }
  }
  mx = max(mx, n - sz);
  if (mx < mi) rot = r, mi = mx;
  return sz;
}
void Dfs2(int x, int fa, int d) {
  q[d].push(Node(-x, d));
  si[d]++;
  be[x] = d;
  for (int i = fir[x]; i; i = nex[i])
    if (tar[i] != fa) Dfs2(tar[i], x, d);
}
int Work(int u) {
  while (que.top().x != q[que.top().y].top().x || q[que.top().y].empty())
    que.pop();
  Node o;
  if (que.top().y == u) o = que.top(), que.pop();
  while (que.top().x != q[que.top().y].top().x || q[que.top().y].empty())
    que.pop();
  u = que.top().y;
  if (o.x) que.push(o);
  return u;
}
int main() {
  Read(n);
  if (n == 1) {
    printf("0\n1\n");
    return 0;
  }
  for (int i = 1; i < n; i++) {
    int u, v, w;
    Read(u), Read(v), Read(w);
    Add(u, v, w), Add(v, u, w);
  }
  Dfs(1, 0);
  q[0].push(Node(-rot, 0));
  que.push(Node(-rot, 0));
  si[0] = 1;
  for (int i = fir[rot]; i; i = nex[i]) {
    Dfs2(tar[i], rot, ++nm);
    Q.push(Node(si[nm] << 1, nm));
    que.push(Node(q[nm].top().x, nm));
  }
  printf("%lld\n", ans1 * 2);
  for (int i = 1; i <= n; i++) {
    while (Q.top().x != si[Q.top().y] + q[Q.top().y].size()) Q.pop();
    if (be[i] == Q.top().y || Q.top().x < n - i + 1)
      m = Work(be[i]);
    else
      m = Q.top().y;
    if (i == rot && -q[m].top().x > rot && !q[0].empty() &&
        Q.top().x < n - i + 1)
      m = 0;
    printf("%d%c", -q[m].top().x, i == n ? 10 : 32);
    q[m].pop();
    si[be[i]]--;
    if (!q[m].empty()) que.push(Node(q[m].top().x, m));
    Q.push(Node(si[m] + q[m].size(), m));
    Q.push(Node(si[be[i]] + q[be[i]].size(), be[i]));
  }
}
