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 N = 1e5 + 5;
forward_list<pair<int, int> > e[N];
inline void add(int x, int y, int w) {
  e[x].push_front(make_pair(y, w));
  e[y].push_front(make_pair(x, w));
}
int n, K;
int siz[N], fa[N];
int bel[N], sum[N], maxp = 0;
int mx[N] = {INT_MAX};
long long dis[N], ans;
void dfs1(int u, int f) {
  siz[u] = 1;
  for (auto v : e[u]) {
    int y = v.first;
    if (y == f) continue;
    dfs1(y, u);
    siz[u] += siz[y];
    mx[u] = max(mx[u], siz[y]);
  }
  mx[u] = max(mx[u], n - siz[u]);
  if (mx[u] < mx[maxp]) maxp = u;
}
void dfs2(int x) {
  ans += dis[x];
  for (auto v : e[x]) {
    int y = v.first, w = v.second;
    if (y == fa[x]) continue;
    fa[y] = x;
    dis[y] = dis[x] + w;
    dfs2(y);
  }
}
set<int> in[N];
set<int> minn;
set<pair<int, int> > st;
void calc(const int &x, const int &rt) {
  bel[x] = rt;
  in[rt].insert(x);
  for (auto v : e[x]) {
    int y = v.first;
    if (y == fa[x]) continue;
    calc(y, rt);
  }
}
void add_link(const int &x, const int &y) {
  const int &p = bel[x], &q = bel[y];
  minn.erase(y);
  if (p) {
    st.erase(make_pair(sum[p], p));
    sum[p]--;
    st.insert(make_pair(sum[p], p));
  }
  if (q) {
    in[q].erase(y);
    if (!in[q].empty()) minn.insert(*in[q].begin());
    st.erase(make_pair(sum[q], q));
    sum[q]--;
    st.insert(make_pair(sum[q], q));
  }
}
int solve(const int &x) {
  int now;
  if (st.rbegin()->first == n - x + 1 && st.rbegin()->second != bel[x])
    now = *in[st.rbegin()->second].begin();
  else
    now = bel[*minn.begin()] != bel[x] || x == maxp ? *minn.begin()
                                                    : *next(minn.begin());
  add_link(x, now);
  return now;
}
int main() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v, w);
  }
  if (n == 1) {
    if (K == 1)
      cout << 0 << endl;
    else
      cout << 0 << endl << 1 << endl;
    return 0;
  }
  dfs1(1, 0);
  dfs2(maxp);
  minn.insert(maxp);
  for (auto v : e[maxp]) {
    int x = v.first;
    calc(x, x);
    minn.insert(*in[x].begin());
    st.insert(make_pair(sum[x] = in[x].size() * 2, x));
  }
  cout << (ans << 1) << endl;
  for (int i = 1; i <= n; i++) cout << solve(i) << " ";
  return 0;
}
