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;
#pragma GCC optimize(0)
const int N = 100010;
int ea[N * 2], eb[N * 2], ec[N], ed[N * 2], etot, rt, n;
int maxsiz[N], ind[N], siz[N], c[N];
long long dis[N], ans;
void addEdge(int x, int y, int z) {
  etot++;
  ea[etot] = y;
  eb[etot] = ec[x];
  ec[x] = etot;
  ed[etot] = z;
}
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -f;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - 48;
    c = getchar();
  }
  return x * f;
}
void dfs(int x, int fa) {
  siz[x] = 1;
  for (int i = ec[x]; i; i = eb[i]) {
    int y = ea[i], z = ed[i];
    if (y == fa) continue;
    dis[y] = dis[x] + z;
    dfs(y, x);
    maxsiz[x] = max(maxsiz[x], siz[y]);
    siz[x] += siz[y];
  }
  maxsiz[x] = max(maxsiz[x], n - siz[x]);
  if (maxsiz[x] < maxsiz[rt] || !rt) rt = x;
}
set<int> st[N], minx;
set<pair<int, int> > s;
void work(int x, int fa, int now) {
  c[x] = now;
  if (c[x]) st[c[x]].insert(x);
  for (int i = ec[x]; i; i = eb[i]) {
    int y = ea[i];
    if (y == fa) continue;
    work(y, x, now ? now : y);
    if (x == rt) {
      siz[y] = st[y].size() * 2;
      s.insert(make_pair(siz[y], y));
      minx.insert(*st[y].begin());
    }
  }
}
int solve(int x) {
  int res;
  if (s.rbegin()->first == n - x + 1 && s.rbegin()->second != c[x]) {
    res = *st[s.rbegin()->second].begin();
  } else {
    if (rt == x || c[*minx.begin()] != c[x])
      res = *minx.begin();
    else
      res = *(++minx.begin());
  }
  minx.erase(res);
  if (c[x]) {
    s.erase(make_pair(siz[c[x]], c[x]));
    siz[c[x]]--;
    s.insert(make_pair(siz[c[x]], c[x]));
  }
  if (c[res]) {
    st[c[res]].erase(res);
    if (!st[c[res]].empty()) minx.insert(*st[c[res]].begin());
    s.erase(make_pair(siz[c[res]], c[res]));
    siz[c[res]]--;
    s.insert(make_pair(siz[c[res]], c[res]));
  }
  return res;
}
signed main() {
  n = read();
  int op = 2;
  if (n == 1) {
    if (op == 1)
      puts("0");
    else
      puts("0\n1");
    fclose(stdin);
    fclose(stdout);
    return 0;
  }
  int maxind = 0;
  for (int i = 1; i <= n - 1; ++i) {
    int x = read(), y = read(), z = read();
    addEdge(x, y, z);
    addEdge(y, x, z);
    ind[x]++;
    ind[y]++;
    maxind = max(maxind, ind[x]);
    maxind = max(maxind, ind[y]);
  }
  dfs(1, 0);
  dis[rt] = 0;
  dfs(rt, 0);
  for (int i = 1; i <= n; ++i) ans += 2 * dis[i];
  printf("%lld\n", ans);
  if (op == 2) {
    work(rt, 0, 0);
    minx.insert(rt);
    for (int i = 1; i <= n; ++i) printf("%d ", solve(i));
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}
