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 long double pi = 3.1415926535897932384626433832795l;
template <typename T>
inline auto sqr(T x) -> decltype(x * x) {
  return x * x;
}
template <typename T>
inline T abs(T x) {
  return x > T() ? x : -x;
}
template <typename T1, typename T2>
inline bool umx(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
inline bool umn(T1& a, T2 b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
const int N = 100000;
struct Input {
  int n;
  vector<pair<int, int> > e[N];
  bool read() {
    if (!(cin >> n)) {
      return 0;
    }
    for (int i = 0; i < int(n - 1); ++i) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      --x;
      --y;
      e[x].push_back(make_pair(y, z));
      e[y].push_back(make_pair(x, z));
    }
    return 1;
  }
  void init(const Input& input) { *this = input; }
};
struct Data : Input {
  long long ans;
  int p[N];
  void write() {
    cout << ans << endl;
    for (int i = 0; i < int(n); ++i) {
      if (i) {
        printf(" ");
      }
      printf("%d", p[i] + 1);
    }
    puts("");
  }
  virtual void solve() {}
  virtual void clear() { *this = Data(); }
};
struct Solution : Data {
  int cnt[N];
  void dfs0(int v, int pr) {
    cnt[v] = 1;
    for (int i = 0; i < int(((int)(e[v]).size())); ++i) {
      if (e[v][i].first != pr) {
        dfs0(e[v][i].first, v);
        cnt[v] += cnt[e[v][i].first];
      }
    }
  }
  int root;
  static const int D = 300;
  int num[N];
  void dfs1(int v, int pr, int c, set<int>& s) {
    num[v] = c;
    s.insert(v);
    for (int i = 0; i < int(((int)(e[v]).size())); ++i) {
      if (e[v][i].first != pr) {
        dfs1(e[v][i].first, v, c, s);
      }
    }
  }
  void solve() {
    dfs0(0, -1);
    for (int i = 0; i < int(n); ++i) {
      for (int j = 0; j < int(((int)(e[i]).size())); ++j) {
        long long s = min(cnt[i], cnt[e[i][j].first]);
        ans += min(s, n - s) * e[i][j].second;
      }
    }
    root = 0;
    while (1) {
      bool done = 0;
      for (int i = 0; i < int(((int)(e[root]).size())); ++i) {
        if (cnt[e[root][i].first] < cnt[root] &&
            2 * cnt[e[root][i].first] > n) {
          root = e[root][i].first;
          done = 1;
        }
      }
      if (!done) {
        break;
      }
    }
    vector<set<int> > s(((int)(e[root]).size()) + 1);
    num[root] = ((int)(e[root]).size());
    s.back().insert(root);
    for (int i = 0; i < int(((int)(e[root]).size())); ++i) {
      dfs1(e[root][i].first, root, i, s[i]);
    }
    vector<set<int> > g((((int)(s).size()) + D - 1) / D);
    for (int i = 0; i < int(((int)(s).size())); ++i) {
      for (auto j : s[i]) {
        g[i / D].insert(j);
      }
    }
    set<pair<int, int> > szs;
    vector<int> ss;
    for (int i = 0; i < int(((int)(s).size())); ++i) {
      ss.push_back((i == ((int)(s).size()) - 1) ? -2 * N
                                                : 2 * ((int)(s[i]).size()));
      szs.insert(make_pair(-ss[i], i));
    }
    int n1 = n;
    for (int i = 0; i < int(n); ++i) {
      if (-szs.begin()->first == n1 && num[i] != szs.begin()->second) {
        p[i] = *s[szs.begin()->second].begin();
      } else {
        p[i] = N;
        for (int j = 0; j < int(((int)(g).size())); ++j) {
          if (j != num[i] / D || i == root) {
            if (((int)(g[j]).size())) {
              umn(p[i], *g[j].begin());
            }
          } else {
            for (int k = 0; k < int(min(D, ((int)(s).size()) - j * D)); ++k) {
              if (j * D + k != num[i]) {
                if (((int)(s[j * D + k]).size())) {
                  umn(p[i], *s[j * D + k].begin());
                }
              }
            }
          }
        }
      }
      szs.erase(make_pair(-ss[num[i]], num[i]));
      ss[num[i]]--;
      szs.insert(make_pair(-ss[num[i]], num[i]));
      szs.erase(make_pair(-ss[num[p[i]]], num[p[i]]));
      ss[num[p[i]]]--;
      szs.insert(make_pair(-ss[num[p[i]]], num[p[i]]));
      n1--;
      s[num[p[i]]].erase(p[i]);
      g[num[p[i]] / D].erase(p[i]);
    }
  }
  void clear() { *this = Solution(); }
};
Solution sol;
int main() {
  cout.setf(ios::showpoint | ios::fixed);
  cout.precision(20);
  sol.read();
  sol.solve();
  sol.write();
  return 0;
}
