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 = 1e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
vector<int> v[maxn], vw[maxn];
int SZ[maxn], n, C;
vector<int> vec[maxn];
int ans[maxn], arr[maxn], col[maxn];
long long SUM;
void dfssz(int u, int par = -1) {
  SZ[u] = 1;
  for (int y : v[u]) {
    if (y != par) {
      dfssz(y, u);
      SZ[u] += SZ[y];
    }
  }
}
int center(int u, int par = -1) {
  for (int y : v[u]) {
    if (y != par && SZ[y] > (n / 2)) return center(y, u);
  }
  return u;
}
void calc(int u, int W = 0, int par = -1) {
  SUM += 2ll * W * SZ[u];
  for (int i = 0; i < int((v[u]).size()); i++) {
    if (v[u][i] == par) continue;
    calc(v[u][i], vw[u][i], u);
  }
}
void put(int u, int par = -1) {
  col[u] = C;
  for (int y : v[u]) {
    if (y != par) put(y, u);
  }
}
void best() {
  for (int i = 1; i <= n; i++) {
    if (ans[i] < arr[i]) return;
    if (arr[i] < ans[i]) {
      memcpy(ans, arr, sizeof ans);
      return;
    }
  }
}
set<pair<int, int> > st, st2;
int delta, pt[maxn], remain[maxn];
void add(int a, int b) {
  int ca = col[a], cb = col[b];
  arr[a] = b;
  delta++;
  st.erase({remain[ca], ca}), st.erase({remain[cb], cb});
  remain[ca]++, remain[cb]++;
  st.insert({remain[ca], ca}), st.insert({remain[cb], cb});
  st2.erase({vec[cb][pt[cb]], cb});
  if (++pt[cb] != int((vec[cb]).size())) st2.insert({vec[cb][pt[cb]], cb});
}
bool solve() {
  st.clear(), st2.clear(), delta = 0;
  for (int i = 0; i < C; i++) vec[i].clear();
  int N = 0;
  for (int i = 1; i <= n; i++) {
    if (col[i] == -1) continue;
    N++, vec[col[i]].push_back(i);
  }
  for (int i = 0; i < C; i++) {
    if (int((vec[i]).size()) > (N / 2)) return 0;
    remain[i] = N - 2 * int((vec[i]).size());
    pt[i] = 0;
    st.insert({remain[i], i});
    st2.insert({vec[i][0], i});
  }
  for (int i = 1; i <= n; i++) {
    if (col[i] == -1) continue;
    int x = st2.begin()->first;
    if (col[i] == col[x]) x = (++st2.begin())->first;
    auto it = st.begin();
    if ((it->first) == delta && col[i] != (it->second) &&
        col[x] != (it->second))
      x = vec[it->second][pt[it->second]];
    add(i, x);
  }
  return 1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    v[a].push_back(b), vw[a].push_back(c);
    v[b].push_back(a), vw[b].push_back(c);
  }
  dfssz(1);
  int r = center(1);
  dfssz(r), calc(r);
  for (int i = 1; i <= n; i++) {
    ans[i] = n + 1 - i;
  }
  memset(col, -1, sizeof col);
  C = 0;
  for (int y : v[r]) put(y, r), C++;
  arr[r] = r;
  if (solve()) best();
  col[r] = C++;
  if (solve()) best();
  cout << SUM << "\n";
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  return cout << "\n", 0;
}
