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, m, i, j, k, x, y, z;
int unmatched, cnt;
struct cmp {
  bool operator()(const pair<int, int> A, const pair<int, int> B) const {
    if (A.first != B.first)
      return A.first > B.first;
    else
      return A.second < B.second;
  }
};
set<pair<int, int>, cmp> Rest;
set<int> s[100010];
set<pair<int, int> > Q;
int getint() {
  int ret = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    ret = ret * 10 + ch - '0';
    ch = getchar();
  }
  return ret;
}
struct Edge {
  int to, w;
  Edge *next;
} edges[200010], *G[100010];
int etop;
void AddEdge(int from, int to, int w) {
  swap(from, w);
  edges[etop] = (Edge){to, w, G[from]};
  G[from] = &edges[etop++];
  edges[etop] = (Edge){from, w, G[to]};
  G[to] = &edges[etop++];
}
typedef int arr[100010];
arr f, size, ok, belong, match, res;
int g, S;
long long d[100010], ans;
void find_G(int x, int fa) {
  size[x] = 1, f[x] = 0;
  for (Edge *e = G[x]; e; e = e->next) {
    if (e->to == fa || ok[e->to] == 1) continue;
    find_G(e->to, x);
    size[x] += size[e->to];
    f[x] = max(f[x], size[e->to]);
  }
  f[x] = max(f[x], S - size[x]);
  if (f[x] < f[g]) g = x;
}
void dfs(int x, int fa) {
  size[x] = 1;
  ans += d[x];
  for (Edge *e = G[x]; e; e = e->next)
    if (e->to != fa) {
      d[e->to] = d[x] + e->w;
      dfs(e->to, x);
      size[x] += size[e->to];
    }
}
void dfs(int x, int fa, int tar) {
  s[tar].insert(x);
  belong[x] = tar;
  for (Edge *e = G[x]; e; e = e->next)
    if (e->to != fa) dfs(e->to, x, tar);
}
void upd(int x, int y) {
  match[x] = *s[y].begin();
  if (x != match[x]) Rest.erase(make_pair(res[belong[x]], belong[x]));
  Q.erase(make_pair(match[x], y)), Rest.erase(make_pair(res[y], y));
  s[y].erase(match[x]);
  res[belong[x]]--, res[y]--;
  if (s[y].size() > 0) Q.insert(make_pair(*s[y].begin(), y));
  Rest.insert(make_pair(res[belong[x]], belong[x]));
  if (x != match[x]) Rest.insert(make_pair(res[y], y));
}
int main() {
  n = getint();
  for (i = 1; i < n; i++) AddEdge(getint(), getint(), getint());
  f[g = 0] = S = n;
  find_G(1, 0);
  dfs(g, 0);
  printf("%I64d\n", ans * 2);
  belong[g] = 0;
  s[0].insert(g);
  Rest.insert(make_pair(2, 0));
  for (Edge *e = G[g]; e; e = e->next) {
    ++cnt;
    Rest.insert(make_pair(res[cnt] = 2 * size[e->to], cnt));
    dfs(e->to, g, cnt);
  }
  res[0] = 2;
  Q.insert(make_pair(g, 0));
  for (i = 1; i <= cnt; i++) Q.insert(make_pair(*s[i].begin(), i));
  for (unmatched = n, i = 1; unmatched && i <= n; unmatched--, i++) {
    if (Rest.begin()->first == unmatched && belong[i] != Rest.begin()->second &&
        Rest.begin()->second != 0) {
      upd(i, Rest.begin()->second);
      continue;
    }
    set<pair<int, int> >::iterator it = Q.begin();
    if (i != g && it->second == belong[i]) it++;
    upd(i, it->second);
  }
  for (i = 1; i <= n; i++) printf("%d ", match[i]);
  return 0;
}
