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;
int n, t;
int A[200006];
vector<pair<int, int> > G[200006];
int siz[200006], rt;
void dfs(int u, int f) {
  siz[u] = 1;
  int mxs = 0;
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i].first;
    if (v == f) continue;
    dfs(v, u);
    siz[u] += siz[v];
    mxs = max(mxs, siz[v]);
  }
  mxs = max(mxs, n - siz[u]);
  if (mxs <= n / 2) rt = u;
}
long long dis[200006], re = 0;
int bel[200006];
void dfs2(int u, int f) {
  re += dis[u];
  siz[u] = 1;
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i].first;
    if (v == f) continue;
    dis[v] = dis[u] + G[u][i].second;
    dfs2(v, u);
    siz[u] += siz[v];
  }
}
int sum[200006];
set<int> idx, rr[200006];
set<pair<int, int> > S;
void afs(int u, int f) {
  rr[bel[u]].insert(u);
  for (auto t : G[u])
    if (t.first != f) bel[t.first] = bel[u], afs(t.first, u);
}
int wkr(int u) {
  int x = bel[u], y = 0;
  if (S.rbegin()->first == n - u + 1 && sum[x] != n - u + 1)
    y = *rr[S.rbegin()->second].begin();
  else if (bel[*idx.begin()] != x || u == rt)
    y = *idx.begin();
  else
    y = *(++idx.begin());
  idx.erase(y);
  int ty = bel[y];
  if (x)
    S.erase(make_pair(sum[x], x)), --sum[x], S.insert(make_pair(sum[x], x));
  if (ty) {
    rr[ty].erase(y);
    if (rr[ty].size()) idx.insert(*rr[ty].begin());
    S.erase(make_pair(sum[ty], ty)), --sum[ty],
        S.insert(make_pair(sum[ty], ty));
  }
  return y;
}
void solve() {
  cin >> n;
  for (int i = (2), iend = (n); i <= iend; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    G[u].push_back(make_pair(v, w)), G[v].push_back(make_pair(u, w));
  }
  if (n == 1) {
    puts("0");
    return void(puts("1"));
  }
  dfs(1, 1);
  dfs2(rt, rt);
  printf("%lld\n", re * 2);
  idx.insert(rt);
  for (auto t : G[rt]) {
    int u = t.first;
    bel[u] = u, afs(u, rt);
    idx.insert(*rr[u].begin());
    sum[u] = siz[u] << 1;
    S.insert(make_pair(sum[u], u));
  }
  for (int i = (1), iend = (n); i <= iend; ++i) printf("%d ", wkr(i));
}
signed main() { solve(); }
