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 ll = long long;
using pii = std::pair<int, int>;
const int N = 1e5 + 10;
template <typename T = int>
inline T read() {
  T x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
int tot = 1, fir[N], nex[N << 1], got[N << 1], tak[N << 1];
inline void AddEdge(int u, int v, int w) {
  nex[++tot] = fir[u], fir[u] = tot, got[tot] = v, tak[tot] = w;
  nex[++tot] = fir[v], fir[v] = tot, got[tot] = u, tak[tot] = w;
}
int siz[N], Max[N], sum[N], bl[N], p[N], g;
ll ans;
inline void dfs(int u, int fa, int n) {
  siz[u] = 1, Max[u] = 0;
  for (int i = fir[u]; i; i = nex[i])
    if (got[i] != fa)
      dfs(got[i], u, n), siz[u] += siz[got[i]],
          Max[u] = std::max(Max[u], siz[got[i]]);
  Max[u] = std::max(Max[u], n - siz[u]);
  if (!g || Max[g] > Max[u]) g = u;
}
std::set<pii, std::greater<pii>> s;
std::set<int> idx[N], Min;
inline void Dfs(int u, int fa, int bl) {
  siz[u] = 1, idx[bl].insert(u), ::bl[u] = bl;
  for (int i = fir[u]; i; i = nex[i])
    if (got[i] != fa)
      Dfs(got[i], u, bl), siz[u] += siz[got[i]],
          ans += 1LL * siz[got[i]] * tak[i];
}
int main() {
  int n = read();
  for (int i = 1; i <= n - 1; ++i) {
    int u = read(), v = read();
    AddEdge(u, v, read());
  }
  dfs(1, 0, n);
  for (int i = fir[g]; i; i = nex[i]) {
    Dfs(got[i], g, got[i]), ans += 1LL * siz[got[i]] * tak[i],
        sum[got[i]] = 2 * siz[got[i]];
    Min.insert(*idx[got[i]].begin()),
        s.insert(std::make_pair(2 * siz[got[i]], got[i]));
  }
  std::cout << (ans << 1) << std::endl;
  Min.insert(g), idx[g].insert(g), s.insert(std::make_pair(2, g)), sum[g] = 2,
                                                                   bl[g] = g;
  for (int i = 1; i <= n; ++i) {
    int Max = (*s.begin()).first, Maxid = (*s.begin()).second;
    if (Max == n - i + 1 && bl[i] != Maxid && Maxid != g) {
      int id = *idx[Maxid].begin();
      p[i] = id;
      idx[Maxid].erase(id), Min.erase(id);
      if (!idx[Maxid].empty()) Min.insert(*idx[Maxid].begin());
    } else {
      int id = *Min.begin();
      if (bl[id] == bl[i] && i != g) {
        std::set<int>::iterator it = Min.begin();
        id = *(++it);
      }
      p[i] = id;
      idx[bl[id]].erase(id), Min.erase(id);
      if (!idx[bl[id]].empty()) Min.insert(*idx[bl[id]].begin());
    }
    s.erase(std::make_pair(sum[bl[i]], bl[i])),
        s.insert(std::make_pair(--sum[bl[i]], bl[i]));
    s.erase(std::make_pair(sum[bl[p[i]]], bl[p[i]])),
        s.insert(std::make_pair(--sum[bl[p[i]]], bl[p[i]]));
  }
  for (int i = 1; i <= n; ++i) printf("%d ", p[i]);
  return 0;
}
