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 <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
const int INF = 5e8;
int n;
vector<pair<int, int> > g[100005];
int mark[100005];
int size[100005], par[100005];
int prep(int v, int p) {
  size[v] = 1;
  par[v] = p;
  int mxsize = -1;
  for (auto e : g[v]) {
    if (e.first == p) continue;
    size[v] += prep(e.first, v);
    chmax(mxsize, size[e.first]);
  }
  chmax(mxsize, n - size[v]);
  if (mxsize * 2 < n)
    mark[v] = 2;
  else if (mxsize * 2 <= n)
    mark[v] = 1;
  return size[v];
}
vector<int> group[100005];
int belong[100005];
long long int dfs(int v, int p, long long int d, int p2) {
  if (p2 != -1) {
    belong[v] = p2;
    group[p2].push_back(v);
  } else {
    belong[v] = v;
    group[v].push_back(v);
  }
  long long int res = d;
  for (auto e : g[v]) {
    if (e.first == p) continue;
    res += dfs(e.first, v, d + e.second, (p2 == -1 ? e.first : p2));
  }
  return res;
}
vector<int> ans;
struct segtree {
  static const int MAX_N = 400005;
  pair<int, int> val[MAX_N];
  int n;
  int all;
  void init(int n_) {
    n = 1;
    all = 0;
    while (n < n_) n <<= 1;
    for (int i = 0; i < (n * 2); ++i) val[i].first = INF;
    for (int i = 0; i < (n_); ++i) val[i + n - 1] = make_pair(INF, i);
    for (int i = n - 2; i >= 0; --i)
      val[i] = min(val[i * 2 + 1], val[i * 2 + 2]);
  }
  void fix(int k) {
    while (k > 0) {
      k = (k - 1) / 2;
      val[k] = min(val[k * 2 + 1], val[k * 2 + 2]);
    }
  }
  void set(int k, int a) {
    k += n - 1;
    val[k].first = a;
    fix(k);
  }
  void add(int k) {
    k += n - 1;
    ++val[k].first;
    fix(k);
  }
  void decr() { ++all; }
  pair<int, int> query() {
    return make_pair(val[0].first - all, val[0].second);
  }
};
bool used[100005];
segtree seg;
void fix(int& a, int& b) {
  while (used[a]) ++a;
  chmax(b, a + 1);
  while (b < n && (belong[a] == belong[b] || used[b])) ++b;
}
long long int solve(int r, bool flag) {
  seg.init(n);
  for (int i = 0; i < (n); ++i) group[i].clear();
  memset((used), 0, sizeof(used));
  ans.resize(n);
  if (flag) {
    used[r] = 1;
    ans[r] = r;
  }
  long long int res = dfs(r, -1, 0, -1) * 2;
  int whole = n;
  if (flag) whole = n - 1;
  for (int i = 0; i < (n); ++i)
    if (group[i].size() > 0) {
      if (flag && i == r) continue;
      seg.set(i, whole - group[i].size() * 2);
    }
  for (int i = 0; i < (n); ++i)
    sort((group[i]).begin(), (group[i]).end(), greater<int>());
  int p1 = 0, p2 = 0;
  fix(p1, p2);
  debug(belong, belong + n);
  ;
  ;
  ;
  ;
  for (int i = 0; i < (n); ++i) {
    if (flag && i == r) continue;
    int g = belong[i];
    pair<int, int> mini = seg.query();
    ;
    ;
    if (mini.first == 0 && mini.second != g) {
      int g2 = mini.second, val = group[g2].back();
      ans[i] = val;
      group[g2].pop_back();
      used[val] = 1;
      seg.add(g);
      seg.add(g2);
      seg.decr();
    } else {
      int val;
      if (belong[p1] == g)
        val = p2;
      else
        val = p1;
      ;
      ;
      ans[i] = val;
      group[belong[val]].pop_back();
      used[val] = 1;
      seg.add(g);
      seg.add(belong[val]);
      seg.decr();
    }
    fix(p1, p2);
  }
  debug((ans).begin(), (ans).end());
  return res;
}
int main() {
  cin >> n;
  for (int i = 0; i < (n - 1); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    g[a].push_back(make_pair(b, c));
    g[b].push_back(make_pair(a, c));
  }
  prep(0, -1);
  vector<int> ans2;
  long long int res = 0;
  ;
  ;
  for (int i = 0; i < (n); ++i)
    if (mark[i]) {
      chmax(res, solve(i, 0));
      if (ans2.empty() || ans2 > ans) ans2 = ans;
      if (mark[i] == 2) chmax(res, solve(i, 1));
      if (ans2.empty() || ans2 > ans) ans2 = ans;
    }
  cout << res << endl;
  for (int i = 0; i < (n); ++i)
    printf("%d%c", ans2[i] + 1, i == n - 1 ? '\n' : ' ');
  return 0;
}
