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, from, to, diss, head[100010], num, size[100010], t, maxn[100010], d;
long long sum;
struct xx {
  int next, to, dis;
} way[200010];
void add(int from, int to, int dis) {
  way[++num].next = head[from];
  way[num].to = to;
  way[num].dis = dis;
  head[from] = num;
}
void dfs(int x, int fa) {
  size[x] = 1;
  for (int i = head[x]; i; i = way[i].next) {
    int y = way[i].to;
    if (y == fa) continue;
    dfs(y, x);
    size[x] += size[y];
    maxn[x] = max(maxn[x], size[y]);
  }
  maxn[x] = max(maxn[x], n - size[x]);
  if (maxn[x] <= n / 2) d = x;
}
long long h[100010];
int c[100010], o, w[100010], ans[100010];
set<int> s[100010];
set<int>::iterator it;
set<int> v;
priority_queue<pair<int, int> > q;
void geth(int x, int fa) {
  for (int i = head[x]; i; i = way[i].next) {
    int y = way[i].to;
    if (y == fa) continue;
    h[y] = h[x] + way[i].dis;
    sum += h[y];
    geth(y, x);
  }
}
void rs(int x, int fa) {
  c[x] = o;
  s[o].insert(x);
  for (int i = head[x]; i; i = way[i].next) {
    int y = way[i].to;
    if (y == fa) continue;
    rs(y, x);
  }
}
void work(int x) {
  geth(x, 0);
  o++;
  c[x] = o;
  w[o] = 1;
  s[o].insert(x);
  o++;
  w[o] = 1;
  q.push(make_pair(w[1], 1));
  q.push(make_pair(w[2], 2));
  v.insert(x);
  for (int i = head[x]; i; i = way[i].next) {
    int y = way[i].to;
    o++;
    rs(y, x);
    w[o] = s[o].size() * 2;
    q.push(make_pair(w[o], o));
    v.insert(*s[o].begin());
  }
  int co;
  for (int i = 1; i <= n; ++i) {
    if (i == x)
      co = 2;
    else
      co = c[i];
    while (w[q.top().second] != q.top().first) q.pop();
    int oo = q.top().second;
    if (w[oo] == n - i + 1 && co != oo && s[oo].size() > 0) {
      ans[i] = (*s[oo].begin());
      int uu = (*s[oo].begin());
      s[oo].erase(s[oo].begin());
      v.erase(uu);
      if (s[oo].size()) v.insert((*s[oo].begin()));
      w[oo]--;
      q.push(make_pair(w[oo], oo));
    } else {
      int d = *v.begin();
      if (c[d] == co) {
        it = v.begin();
        it++;
      } else
        it = v.begin();
      ans[i] = *it;
      int u = *it;
      v.erase(it);
      s[c[u]].erase(u);
      if (s[c[u]].size()) v.insert((*s[c[u]].begin()));
      w[c[u]]--;
      q.push(make_pair(w[c[u]], c[u]));
    }
    w[co]--;
    q.push(make_pair(w[co], co));
  }
}
int read() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x;
}
int main() {
  n = read();
  for (int i = 1; i < n; ++i) {
    from = read();
    to = read();
    diss = read();
    add(from, to, diss);
    add(to, from, diss);
  }
  dfs(1, 0);
  work(d);
  cout << sum * 2 << endl;
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  return 0;
}
