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 t, next, v;
} g[410001];
vector<int> a[210001];
long long dep[210001], ans;
int sz[210001], f[210001], i, j, k, n, tot, h[210001], b[210001], bl[210001],
    t1, rt, m, p[210001];
struct stcmp {
  bool operator()(int x, int y) { return b[x] > b[y] || b[x] == b[y] && x < y; }
};
set<int, stcmp> s;
set<int> w;
bool cmp(int x, int y) { return x > y; }
void addedge(int x, int y, int z) {
  g[++tot].t = y;
  g[tot].next = h[x];
  h[x] = tot;
  g[tot].v = z;
  g[++tot].t = x;
  g[tot].next = h[y];
  h[y] = tot;
  g[tot].v = z;
}
void dfs0(int x, int fa) {
  int i;
  sz[x] = 1;
  f[x] = 0;
  for (i = h[x]; i; i = g[i].next)
    if (fa != g[i].t)
      dfs0(g[i].t, x), sz[x] += sz[g[i].t], f[x] = max(f[x], sz[g[i].t]);
}
void dfs1(int x, int fa) {
  int i;
  a[bl[x]].push_back(x);
  ans += 2LL * dep[x];
  for (i = h[x]; i; i = g[i].next)
    if (fa != g[i].t) {
      dep[g[i].t] = dep[x] + g[i].v;
      if (x == rt)
        bl[g[i].t] = ++m;
      else
        bl[g[i].t] = bl[x];
      dfs1(g[i].t, x);
    }
}
int main() {
  scanf("%d", &n);
  tot = 0;
  memset(h, 0, sizeof(h));
  for (i = 1; i < n; i++) scanf("%d%d%d", &j, &k, &t1), addedge(j, k, t1);
  if (n == 1) {
    puts("0\n1");
    return 0;
  }
  dfs0(1, 0);
  for (k = i = 1; i <= n; i++) {
    a[i].clear();
    f[i] = max(f[i], sz[1] - sz[i]);
    if (f[i] < f[k]) k = i;
  }
  rt = k;
  m = 1;
  bl[rt] = 1;
  dep[rt] = ans = 0;
  dfs1(rt, 0);
  printf("%lld\n", ans);
  w.clear();
  s.clear();
  for (i = 1; i <= m; i++) {
    sort(a[i].begin(), a[i].end(), cmp);
    b[i] = 2 * a[i].size();
    if (i > 1) s.insert(i);
    w.insert(a[i].back());
  }
  for (i = 1; i <= n; i++) {
    k = bl[i];
    if (k > 1) s.erase(k);
    if (!s.empty())
      j = *s.begin();
    else
      j = -1;
    if (j != -1 && b[j] == n - i + 1) {
      t1 = a[j].back();
      w.erase(t1);
      a[j].pop_back();
      if (!a[j].empty()) w.insert(a[j].back());
    } else {
      t1 = *w.begin();
      if (bl[t1] == k && k > 1) t1 = *w.upper_bound(t1);
      j = bl[t1];
      w.erase(t1);
      a[j].pop_back();
      if (!a[j].empty()) w.insert(a[j].back());
    }
    p[i] = t1;
    if (bl[t1] != 1) s.erase(bl[t1]);
    b[k]--;
    b[bl[t1]]--;
    if (k > 1) s.insert(k);
    if (bl[t1] > 1) s.insert(bl[t1]);
  }
  for (i = 1; i <= n; i++) printf("%d%c", p[i], (i == n) ? '\n' : ' ');
  return 0;
}
