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;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
vector<pair<int, int> > adj[100100];
long long dep[100100];
int sz[100100], mx[100100];
void dfs(int u, int f = 0) {
  sz[u] = 1;
  for (pair<int, int> p : adj[u]) {
    int v = p.first;
    if (v == f) continue;
    dfs(v, u);
    sz[u] += sz[v];
    smax(mx[u], sz[v]);
  }
}
int n, p[100100];
int id[100100];
set<int> s[100100];
void dfs1(int u, int top, int f) {
  id[u] = top;
  s[top].insert(u);
  for (pair<int, int> p : adj[u]) {
    int v = p.first;
    if (v == f) continue;
    dep[v] = dep[u] + p.second;
    dfs1(v, top, u);
  }
}
int tmp[100100];
long long solve(int u) {
  int cnt = 1;
  id[u] = 1;
  s[1].insert(u);
  dep[u] = 0;
  for (pair<int, int> p : adj[u]) {
    int v = p.first;
    dep[v] = p.second;
    dfs1(v, ++cnt, u);
  }
  set<pair<int, int> > sz_id;
  set<int> mns;
  for (int i = 1; i <= cnt; i++)
    sz_id.insert(pair<int, int>(sz[i] = 2 * s[i].size(), i));
  for (int i = 1; i <= cnt; i++) mns.insert(*s[i].begin());
  for (int i = 1; i < n; i++) {
    int id = ::id[i];
    sz_id.erase(pair<int, int>(sz[id], id));
    sz_id.insert(pair<int, int>(--sz[id], id));
    int can;
    if (sz_id.rbegin()->first > n - i) {
      int num = sz_id.rbegin()->second;
      if (num == 1)
        can = *mns.begin();
      else
        can = *s[num].begin();
    } else {
      auto it = mns.begin();
      if (id > 1 && ::id[*it] == id) it++;
      can = *it;
    }
    id = ::id[can];
    s[id].erase(can);
    mns.erase(can);
    p[i] = can;
    if (!s[id].empty()) mns.insert(*s[id].begin());
    sz_id.erase(pair<int, int>(sz[id], id));
    sz_id.insert(pair<int, int>(--sz[id], id));
  }
  p[n] = *mns.begin();
  long long ans = 0;
  for (int i = 1; i <= n; i++) ans += dep[i];
  ans <<= 1;
  return ans;
}
int main() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    gn(u, v);
    gn(w);
    adj[u].push_back(pair<int, int>(v, w));
    adj[v].push_back(pair<int, int>(u, w));
  }
  dfs(1);
  for (int i = 1; i <= n; i++) {
    if (sz[i] * 2 >= n && mx[i] * 2 <= n) {
      cout << solve(i) << endl;
      break;
    }
  }
  for (int i = 1; i <= n; i++) printf("%d ", p[i]);
  return 0;
}
