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;
long long ans = 0;
long long n;
const long long N = 3e5 + 100;
long long _sz[N];
vector<pair<long long, long long> > g[N];
void dfs(long long v, long long p = -1) {
  _sz[v] = 1;
  for (auto to : g[v]) {
    if (to.first != p) {
      dfs(to.first, v);
      ans += 1LL * 2 * to.second * min(n - _sz[to.first], _sz[to.first]);
      _sz[v] += _sz[to.first];
    }
  }
}
long long centroid(long long v, long long sz1, long long p = -1) {
  for (auto to : g[v]) {
    if (to.first != p && _sz[to.first] * 2 > sz1) {
      return centroid(to.first, sz1, v);
    }
  }
  return v;
}
long long tin[N], tout[N];
set<long long> st1;
long long up[N];
long long timer = 0;
void dfs1(long long v, long long p, long long pr) {
  tin[v] = ++timer;
  up[v] = pr;
  _sz[v] = 1;
  for (auto to : g[v]) {
    if (to.first != p) {
      dfs1(to.first, v, pr);
      _sz[v] += _sz[to.first];
    }
  }
  tout[v] = timer;
}
long long Tree[N * 4];
void modify(long long v, long long l, long long r, long long x, long long val) {
  if (l == r) {
    Tree[v] = val;
    return;
  }
  long long m = (r + l) / 2;
  if (x <= m) {
    modify(v * 2, l, m, x, val);
  } else {
    modify(v * 2 + 1, m + 1, r, x, val);
  }
  Tree[v] = min(Tree[v * 2], Tree[v * 2 + 1]);
}
long long query(long long v, long long l, long long r, long long al,
                long long ar) {
  if (l >= al && r <= ar) {
    return Tree[v];
  }
  long long m = (r + l) / 2;
  if (al > m) {
    return query(v * 2 + 1, m + 1, r, al, ar);
  }
  if (ar <= m) {
    return query(v * 2, l, m, al, ar);
  }
  return min(query(v * 2, l, m, al, ar), query(v * 2 + 1, m + 1, r, al, ar));
}
long long query(long long u, long long k) {
  if (k == 0) {
    if (tout[u] == n) {
      return query(1, 1, n, 1, tin[u] - 1);
    } else {
      return min(query(1, 1, n, 1, tin[u] - 1), query(1, 1, n, tout[u] + 1, n));
    }
  } else {
    return query(1, 1, n, tin[u], tout[u]);
  }
}
long long p[N];
set<long long> ts[N];
signed main() {
  cin >> n;
  for (long long i = 0; i < n - 1; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  dfs(1);
  cout << ans << "\n";
  long long c = centroid(1, _sz[1]);
  tin[c] = ++timer;
  for (auto to : g[c]) {
    dfs1(to.first, c, to.first);
    _sz[to.first] *= 2;
    if (_sz[to.first] > n) {
      cout << "A";
      return 0;
    }
    ts[_sz[to.first]].insert(to.first);
  }
  tout[c] = 1;
  up[c] = c;
  for (long long i = 1; i <= n; i++) {
    modify(1, 1, n, tin[i], i);
  }
  vector<long long> must;
  for (long long i = 1; i <= n; i++) {
    must.clear();
    for (auto it = ts[n - i + 1].begin(); it != ts[n - i + 1].end(); it++) {
      must.push_back(*it);
    }
    if ((long long)must.size() == 2) {
      p[i] = query(must[up[i] == must[0]], 1);
    } else if ((long long)must.size() == 1) {
      if (up[i] == must[0]) {
        p[i] = query(up[i], 0);
      } else {
        p[i] = query(must[0], 1);
      }
    } else {
      if (i == c) {
        p[i] = Tree[1];
      } else {
        p[i] = query(up[i], 0);
      }
    }
    modify(1, 1, n, tin[p[i]], 1 << 30);
    long long u = up[i];
    long long v = up[p[i]];
    if (u != c) {
      ts[_sz[u]].erase(u);
      ts[--_sz[u]].insert(u);
    }
    if (v != c) {
      ts[_sz[v]].erase(v);
      ts[--_sz[v]].insert(v);
    }
  }
  for (long long i = 1; i <= n; i++) {
    cout << p[i] << " ";
  }
  return 0;
}
