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;
const int M = 100005;
int read() {
  int x = 0, flag = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') flag = -1;
  while (c >= '0' && c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return x * flag;
}
int n, tot, rt, Min = 0x3f3f3f3f, f[M], siz[M], bel[M];
long long ans, dis[M];
set<int> in[M], minn;
set<pair<int, int> > Set;
struct edge {
  int v, c, next;
  edge(int V = 0, int C = 0, int N = 0) : v(V), c(C), next(N) {}
} e[2 * M];
void dfs1(int u, int fa) {
  int Max = 0;
  siz[u] = 1;
  for (int i = f[u]; i; i = e[i].next) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    Max = max(Max, siz[v]);
  }
  Max = max(Max, n - siz[u]);
  if (Max < Min) {
    Min = Max;
    rt = u;
  }
}
void dfs2(int u, int fa) {
  ans += dis[u];
  for (int i = f[u]; i; i = e[i].next) {
    int v = e[i].v, c = e[i].c;
    if (v == fa) continue;
    dis[v] = dis[u] + c;
    dfs2(v, u);
  }
}
void dfs3(int u, int fa, int tp) {
  bel[u] = tp;
  in[tp].insert(u);
  for (int i = f[u]; i; i = e[i].next) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs3(v, u, tp);
  }
}
void link(int u, int v) {
  int x = bel[u], y = bel[v];
  minn.erase(v);
  if (x) {
    Set.erase(make_pair(siz[x], x));
    Set.insert(make_pair(--siz[x], x));
  }
  if (y) {
    in[y].erase(v);
    if (!in[y].empty()) minn.insert(*in[y].begin());
    Set.erase(make_pair(siz[y], y));
    Set.insert(make_pair(--siz[y], y));
  }
}
int solve(int i) {
  int ret = 0;
  if (Set.rbegin()->first == n - i + 1 && Set.rbegin()->second != bel[i])
    ret = *in[Set.rbegin()->second].begin();
  else {
    set<int>::iterator it = minn.begin();
    it++;
    ret = (bel[i] != bel[*minn.begin()] || i == rt) ? (*minn.begin()) : (*it);
  }
  link(i, ret);
  return ret;
}
int main() {
  n = read();
  for (int i = 1; i <= n - 1; i++) {
    int u = read(), v = read(), c = read();
    e[++tot] = edge(v, c, f[u]), f[u] = tot;
    e[++tot] = edge(u, c, f[v]), f[v] = tot;
  }
  dfs1(1, 0);
  dfs2(rt, 0);
  printf("%lld\n", ans * 2);
  if (n == 1) {
    puts("1");
    return 0;
  }
  minn.insert(rt);
  for (int i = f[rt]; i; i = e[i].next) {
    int v = e[i].v;
    dfs3(v, rt, v);
    siz[v] = in[v].size() * 2;
    minn.insert(*in[v].begin());
    Set.insert(make_pair(siz[v], v));
  }
  for (int i = 1; i <= n; i++) printf("%d ", solve(i));
}
