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>
#pragma warning(disable : 4996)
using namespace std;
int n;
vector<pair<long long, long long>> edge[200000];
int child[200000];
int u;
long long d[200000];
long long dsum;
void back(int now, int parent) {
  int sum = 0;
  for (auto e : edge[now]) {
    if (e.first == parent) continue;
    back(e.first, now);
    sum += child[e.first];
  }
  child[now] = sum + 1;
}
void back2(int now, int parent) {
  int ma = 0, mai;
  for (auto e : edge[now]) {
    if (e.first == parent) continue;
    if (ma < child[e.first]) {
      ma = child[e.first];
      mai = e.first;
    }
  }
  if (ma > n / 2) {
    back2(mai, now);
  } else {
    u = now;
  }
}
void back3(int now, int parent) {
  dsum += d[now];
  for (auto e : edge[now]) {
    if (e.first == parent) continue;
    d[e.first] = d[now] + e.second;
    back3(e.first, now);
  }
}
int group[200000];
vector<int> gnum[200000];
int groupi;
set<int> gset[200000];
int gsize[200000];
set<pair<int, int>, greater<pair<int, int>>> gs;
set<int> small;
void back4(int now, int parent) {
  group[now] = groupi;
  gset[groupi].insert(now);
  gsize[groupi] += 2;
  for (auto e : edge[now]) {
    if (e.first == parent) continue;
    back4(e.first, now);
  }
}
int main() {
  int i, j, k;
  scanf("%d", &n);
  for (i = 0; i < n - 1; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    x--, y--;
    edge[x].push_back(pair<long long, long long>(y, z));
    edge[y].push_back(pair<long long, long long>(x, z));
  }
  back(0, -1);
  back2(0, -1);
  back3(u, -1);
  printf("%I64d\n", 2 * dsum);
  gset[groupi].insert(u);
  group[u] = 0;
  gsize[groupi] += 2;
  groupi++;
  for (auto e : edge[u]) back4(e.first, u), groupi++;
  for (i = 0; i < groupi; i++)
    gs.insert(pair<int, int>(gsize[i], i)), small.insert(*gset[i].begin());
  for (i = 0; i < n; i++) {
    int x = group[i];
    auto it = gs.find(pair<int, int>(gsize[x], x));
    gs.erase(it);
    gsize[x]--;
    gs.insert(pair<int, int>(gsize[x], x));
    int y;
    if (gs.begin()->first >= n - i && gs.begin()->second != 0) {
      y = gs.begin()->second;
    } else {
      if (group[*small.begin()] != x || x == 0) {
        y = group[*small.begin()];
      } else {
        auto it = small.begin();
        it++;
        y = group[*it];
      }
    }
    printf("%d ", *gset[y].begin() + 1);
    it = gs.find(pair<int, int>(gsize[y], y));
    gs.erase(it);
    gsize[y]--;
    gs.insert(pair<int, int>(gsize[y], y));
    small.erase(*gset[y].begin());
    gset[y].erase(gset[y].begin());
    if (gset[y].size()) small.insert(*gset[y].begin());
  }
  return 0;
}
