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 maxn = 100050;
int n, ans2[maxn];
long long ans1 = 0;
int es = 0, he[maxn] = {0}, to[maxn * 2], ne[maxn * 2], di[maxn * 2];
int g, fa[maxn], siz[maxn];
long long dep[maxn];
int bel[maxn];
vector<int> sub[maxn];
int ss = 0, cur[maxn];
int cnt[maxn];
set<pair<int, int> > sz, v;
void ins(int x, int y, int d) {
  to[++es] = y;
  ne[es] = he[x];
  he[x] = es;
  di[es] = d;
}
void bfs(int S) {
  int qu[maxn], en = 0;
  fa[qu[en++] = S] = 0;
  dep[S] = 0;
  for (int i = 0; i < en; i++) {
    int x = qu[i];
    for (int j = he[x]; j; j = ne[j])
      if (to[j] != fa[x]) {
        fa[qu[en++] = to[j]] = x;
        dep[to[j]] = dep[x] + di[j];
      }
  }
  for (int i = en - 1; i >= 0; i--) {
    int x = qu[i];
    siz[x] = 1;
    for (int j = he[x]; j; j = ne[j])
      if (to[j] != fa[x]) siz[x] += siz[to[j]];
  }
}
int get_g() {
  bfs(1);
  for (int i = 1; i <= n; i++) {
    bool check = !(n - siz[i] > (n / 2));
    for (int j = he[i]; j; j = ne[j])
      if (to[j] != fa[i] && siz[to[j]] > n / 2) check = false;
    if (check) return i;
  }
}
void add(int x, int c) {
  bel[x] = c;
  sub[c].push_back(x);
  for (int i = he[x]; i; i = ne[i])
    if (to[i] != fa[x]) add(to[i], c);
}
int main() {
  scanf("%d", &n);
  int n0 = n;
  for (int i = 1; i < n; i++) {
    int x, y, d;
    scanf("%d %d %d", &x, &y, &d);
    ins(x, y, d);
    ins(y, x, d);
  }
  int g = get_g();
  bfs(g);
  ans1 = 0;
  for (int i = 1; i <= n; i++) ans1 += dep[i];
  ans1 *= 2;
  for (int i = he[g]; i; i = ne[i]) add(to[i], ss++);
  for (int i = 0; i < ss; i++) sort(sub[i].begin(), sub[i].end());
  for (int i = 0; i < ss; i++) {
    sz.insert(make_pair(cnt[i] = sub[i].size() * 2, i));
    v.insert(make_pair(sub[i][0], i));
  }
  v.insert(make_pair(g, ss));
  sub[bel[g] = ss++].push_back(g);
  for (int i = 1; i <= n; i++) {
    int x = bel[i], y;
    sz.erase(make_pair(cnt[x]--, x));
    sz.insert(make_pair(cnt[x], x));
    set<pair<int, int> >::iterator t = sz.end();
    if ((*--t).first <= --n0) {
      t = v.begin();
      if (i != g && (*t).second == x) t++;
      y = (*t).second;
    } else
      y = (*t).second;
    sz.erase(make_pair(cnt[y]--, y));
    sz.insert(make_pair(cnt[y], y));
    v.erase(make_pair(sub[y][cur[y]], y));
    ans2[i] = sub[y][cur[y]++];
    if (cur[y] < sub[y].size()) v.insert(make_pair(sub[y][cur[y]], y));
  }
  printf("%I64d\n", ans1);
  for (int i = 1; i <= n; i++) printf("%d%c", ans2[i], (i < n) ? ' ' : '\n');
  return 0;
}
