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;
struct edge {
  int to, cost;
  edge(int to = 0, int cost = 0) : to(to), cost(cost) {}
};
vector<edge> vec[100005];
vector<int> gt[100005];
int nd[100005], cmb[100005];
int sum[100005], gl[100005];
int pos[100005];
int n;
void dfs(int v = 0, int p = -1) {
  nd[v] = 1;
  for (int i = 0; i < vec[v].size(); i++) {
    int to = vec[v][i].to;
    if (to != p) {
      dfs(to, v);
      nd[v] += nd[to];
    }
  }
}
pair<int, int> center(int v = 0, int p = -1) {
  int mx = n - nd[v];
  pair<int, int> ret = pair<int, int>(n * 2, -1);
  for (int i = 0; i < vec[v].size(); i++) {
    int to = vec[v][i].to;
    if (to != p) {
      pair<int, int> p = center(to, v);
      ret = min(ret, p);
      mx = max(mx, nd[to]);
    }
  }
  ret = min(ret, pair<int, int>(mx, v));
  return ret;
}
void color(int v, int p, int k) {
  cmb[v] = k;
  gt[k].push_back(v);
  for (int i = 0; i < vec[v].size(); i++) {
    int to = vec[v][i].to;
    if (to != p) {
      color(to, v, k);
    }
  }
}
long long int get(int v, int p, long long int d) {
  long long int ret = d;
  for (int i = 0; i < vec[v].size(); i++) {
    edge e = vec[v][i];
    if (e.to != p) {
      ret += get(e.to, v, d + e.cost);
    }
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    a--;
    b--;
    vec[a].push_back(edge(b, c));
    vec[b].push_back(edge(a, c));
  }
  if (n == 1) {
    puts("0");
    puts("1");
    return 0;
  }
  dfs();
  int ct = center().second;
  int sz = 0;
  cmb[ct] = sz;
  gt[sz++].push_back(ct);
  for (int i = 0; i < vec[ct].size(); i++) {
    int to = vec[ct][i].to;
    color(to, ct, sz++);
  }
  set<pair<int, int> > st, gd;
  set<pair<int, int> >::iterator it;
  for (int i = 0; i < sz; i++) {
    sort(gt[i].begin(), gt[i].end());
    sum[i] = gt[i].size() * 2;
    st.insert(pair<int, int>(sum[i], i));
    pos[i] = 0;
    gd.insert(pair<int, int>(gt[i][0], i));
  }
  for (int i = 0; i < n; i++) {
    int c = cmb[i];
    st.erase(pair<int, int>(sum[c], c));
    sum[c]--;
    it = st.end();
    it--;
    pair<int, int> p = *it;
    if (p.first == n - i && p.second != 0) {
      int d = p.second;
      st.erase(it);
      gd.erase(pair<int, int>(gt[d][pos[d]], d));
      gl[i] = gt[d][pos[d]++];
      sum[d]--;
      st.insert(pair<int, int>(sum[d], d));
      if (pos[d] < gt[d].size()) gd.insert(pair<int, int>(gt[d][pos[d]], d));
    } else {
      it = gd.begin();
      if (it->second == c && c != 0) it++;
      int d = it->second;
      st.erase(pair<int, int>(sum[d], d));
      gd.erase(it);
      gl[i] = gt[d][pos[d]++];
      sum[d]--;
      st.insert(pair<int, int>(sum[d], d));
      if (pos[d] < gt[d].size()) gd.insert(pair<int, int>(gt[d][pos[d]], d));
    }
    st.insert(pair<int, int>(sum[c], c));
  }
  printf("%I64d\n", get(ct, -1, 0) * 2LL);
  for (int i = 0; i < n; i++) {
    if (i != 0) printf(" ");
    printf("%d", gl[i] + 1);
  }
  puts("");
  return 0;
}
