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;
pair<long long int, long long int> kd[4 * 100005];
long long int n, u, s[100005], d[100005];
vector<pair<long long int, long long int> > v[100005];
pair<long long int, long long int> update(long long int root, long long int bas,
                                          long long int son, long long int x,
                                          long long int val) {
  if (x < bas or son < x) return kd[root];
  if (bas == son) return kd[root] = make_pair(val, bas);
  return kd[root] = min(update(root * 2, bas, (bas + son) / 2, x, val),
                        update(root * 2 + 1, (bas + son) / 2 + 1, son, x, val));
}
pair<long long int, long long int> query(long long int root, long long int bas,
                                         long long int son, long long int x,
                                         long long int y) {
  if (y < bas or son < x) return make_pair(n + 1, 0);
  if (x <= bas and son <= y) return kd[root];
  return min(query(root * 2, bas, (bas + son) / 2, x, y),
             query(root * 2 + 1, (bas + son) / 2 + 1, son, x, y));
}
void dfs(long long int nod, long long int pre, long long int der) {
  s[nod] = 1;
  d[nod] = der;
  for (typeof(v[nod].begin()) it = v[nod].begin(); it != v[nod].end(); it++) {
    if ((it->first) == pre) continue;
    dfs((it->first), nod, der + (it->second));
    s[nod] += s[it->first];
  }
}
long long int centroid(long long int nod, long long int pre) {
  for (typeof(v[nod].begin()) it = v[nod].begin(); it != v[nod].end(); it++)
    if ((it->first) != pre and s[it->first] > n / 2)
      return centroid(it->first, nod);
  return nod;
}
long long int g, Time, nu[100005], say[100005];
pair<long long int, long long int> arr[100005];
set<pair<long long int, long long int> > S;
priority_queue<pair<long long int, long long int> > Q;
void rec(long long int nod, long long int pre) {
  Time++;
  update(1, 1, n, Time, nod);
  nu[nod] = g;
  for (typeof(v[nod].begin()) it = v[nod].begin(); it != v[nod].end(); it++)
    if ((it->first) != pre) rec(it->first, nod);
}
int main() {
  cin >> n;
  for (long long int i = 1; i <= n - 1; i++) {
    long long int x, y, c;
    cin >> x >> y >> c;
    v[x].push_back(make_pair(y, c));
    v[y].push_back(make_pair(x, c));
  }
  dfs(1, 0, 0);
  long long int u = centroid(1, 0);
  dfs(u, 0, 0);
  long long int firstres = 0;
  for (long long int i = 1; i <= n; i++) firstres += 2 * d[i];
  cout << firstres << endl;
  ++Time;
  arr[++g] = make_pair(Time, Time);
  say[g] = 2;
  Q.push(make_pair(say[g], g));
  update(1, 1, n, Time, u);
  nu[u] = g;
  for (typeof(v[u].begin()) it = v[u].begin(); it != v[u].end(); it++) {
    arr[++g].first = Time + 1;
    rec(it->first, u);
    arr[g].second = Time;
    say[g] = 2 * (arr[g].second - arr[g].first + 1);
    Q.push(make_pair(say[g], g));
  }
  for (long long int i = 1; i <= n; i++) {
    long long int k = n - i + 1;
    while (Q.size() and S.count(Q.top())) Q.pop();
    long long int ok = 1;
    if (Q.size() and Q.top().second == nu[i] and Q.top().first == k) {
      Q.pop();
      Q.push(make_pair(k - 1, nu[i]));
      say[nu[i]]--;
      ok = 0;
    }
    while (Q.size() and S.count(Q.top())) Q.pop();
    if (Q.size() and Q.top().first == k and Q.top().second != nu[u]) {
      long long int al = Q.top().second;
      Q.push(make_pair(k - 1, al));
      Q.pop();
      while (Q.size() and S.count(Q.top())) Q.pop();
      pair<long long int, long long int> r =
          query(1, 1, n, arr[al].first, arr[al].second);
      cout << r.first << " ";
      assert(r.first != n + 1);
      update(1, 1, n, r.second, n + 1);
      if (ok) {
        S.insert(make_pair(say[nu[i]], nu[i]));
        say[nu[i]]--;
        Q.push(make_pair(say[nu[i]], nu[i]));
      }
      continue;
    }
    pair<long long int, long long int> r = make_pair(n + 1, 0);
    if (arr[nu[i]].first != 1)
      r = min(r, query(1, 1, n, 1, arr[nu[i]].first - 1));
    if (arr[nu[i]].second != n)
      r = min(r, query(1, 1, n, arr[nu[i]].second + 1, n));
    if (i == u) r = min(r, query(1, 1, n, arr[nu[i]].first, arr[nu[i]].second));
    cout << r.first << " ";
    assert(r.first != n + 1);
    update(1, 1, n, r.second, n + 1);
    if (ok) {
      S.insert(make_pair(say[nu[i]], nu[i]));
      say[nu[i]]--;
      Q.push(make_pair(say[nu[i]], nu[i]));
    }
    S.insert(make_pair(say[nu[r.first]], nu[r.first]));
    say[nu[r.first]]--;
    Q.push(make_pair(say[nu[r.first]], nu[r.first]));
  }
  cout << endl;
}
