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 = 100000 + 10;
struct P {
  int to, dis;
};
vector<P> v[maxn];
int n;
long long d[maxn];
int dfs(int x, int f, int &id, int &mi) {
  int sz = 1, maxs = 0;
  for (auto i : v[x])
    if (i.to != f) {
      d[i.to] = d[x] + i.dis;
      int tmp = dfs(i.to, x, id, mi);
      sz += tmp;
      maxs = max(maxs, tmp);
    }
  int val = max(maxs, n - sz);
  if (val < mi) mi = val, id = x;
  return sz;
}
void dfs(int x) {
  int id, mi;
  dfs(x, -1, id, mi);
}
void dfs2(int x, int f, set<int> &s) {
  s.insert(x);
  for (auto i : v[x])
    if (i.to != f) dfs2(i.to, x, s);
}
int cent;
set<int> st[maxn], st2;
set<pair<int, int> > st0;
int id[maxn], sz, ioval[maxn];
bool ruse = 0;
inline void sub(int pos) {
  st0.erase(pair<int, int>(ioval[pos], pos));
  ioval[pos]--;
  st0.insert(pair<int, int>(ioval[pos], pos));
}
int solve(int x) {
  if (x != cent) sub(id[x]);
  pair<int, int> r = *st0.rbegin();
  if (r.first == n - x + 1) {
    int pos = r.second, ret = *st[pos].begin();
    st2.erase(*st[pos].begin());
    st[pos].erase(st[pos].begin());
    if (!st[pos].empty()) st2.insert(*st[pos].begin());
    sub(pos);
    return ret;
  }
  int tmp = -1;
  if (x != cent && !st[id[x]].empty()) st2.erase(tmp = *st[id[x]].begin());
  int ret = st2.empty() ? cent : *st2.begin();
  if (!ruse && cent < ret) ruse = 1, ret = cent;
  if (tmp != -1) st2.insert(tmp);
  if (ret == cent) return ret;
  int pos = id[ret];
  sub(pos);
  st2.erase(*st[pos].begin());
  st[pos].erase(st[pos].begin());
  if (!st[pos].empty()) st2.insert(*st[pos].begin());
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int x, y, dis;
    scanf("%d%d%d", &x, &y, &dis);
    v[x].push_back((P){y, dis});
    v[y].push_back((P){x, dis});
  }
  int mi = n;
  dfs(1, -1, cent, mi);
  d[cent] = 0;
  dfs(cent);
  long long ans = 0LL;
  for (int i = 1; i <= n; i++) ans += d[i];
  printf("%I64d\n", 2 * ans);
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  if (n == 2) {
    printf("2 1\n");
    return 0;
  }
  sz = v[cent].size();
  for (int i = 0; i < sz; i++) {
    dfs2(v[cent][i].to, cent, st[i]);
    for (auto j : st[i]) id[j] = i;
  }
  for (int i = 0; i < sz; i++) st2.insert(*st[i].begin());
  for (int i = 0; i < sz; i++)
    st0.insert(pair<int, int>(2 * st[i].size(), i)),
        ioval[i] = 2 * st[i].size();
  for (int i = 1; i <= n; i++) printf("%d%c", solve(i), i == n ? '\n' : ' ');
}
