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 N = 100010;
int n;
vector<pair<int, long long> > e[N];
int rt = 0, sz[N], mn[N];
long long ans;
int a[N];
int cnt = 0, anc[N], num[N];
set<int> s[N];
set<pair<int, int> > st;
set<pair<int, int>, greater<pair<int, int> > > ss;
inline int Max(const int &x, const int &y) { return x > y ? x : y; }
void getrt(int u, int ff) {
  sz[u] = 1;
  for (auto v : e[u])
    if (v.first != ff)
      getrt(v.first, u), sz[u] += sz[v.first], mn[u] = Max(mn[u], sz[v.first]);
  mn[u] = Max(mn[u], n - sz[u]);
  if (mn[rt] > mn[u]) rt = u;
}
void dfs(int u, int ff, int w) {
  sz[u] = 1, anc[u] = w, s[w].insert(u);
  for (auto v : e[u])
    if (v.first != ff) {
      if (!w)
        dfs(v.first, u, ++cnt);
      else
        dfs(v.first, u, w);
      sz[u] += sz[v.first];
      ans += v.second * sz[v.first];
    }
}
void Match(int x, int y) {
  int yy = *s[y].begin();
  a[x] = yy;
  st.erase(make_pair(yy, y)), ss.erase(make_pair(num[y], y));
  if (x != yy) ss.erase(make_pair(num[anc[x]], anc[x]));
  s[y].erase(yy), --num[anc[x]], --num[y];
  if (s[y].size()) st.insert(make_pair(*s[y].begin(), y));
  if (x != yy) ss.insert(make_pair(num[y], y));
  ss.insert(make_pair(num[anc[x]], anc[x]));
}
void solve() {
  dfs(rt, 0, 0);
  for (int i = 0; i <= cnt; i++) st.insert(make_pair(*s[i].begin(), i));
  for (int i = 0; i <= cnt; i++)
    num[i] = s[i].size() * 2, ss.insert(make_pair(num[i], i));
  int sum = n;
  for (int i = 1; i <= n; i++) {
    set<pair<int, int> >::iterator it = ss.begin();
    if (it->first == sum-- && anc[i] != it->second && it->second) {
      Match(i, it->second);
      continue;
    }
    it = st.begin();
    if (i != rt && it->second == anc[i]) ++it;
    Match(i, it->second);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1, x, y, z; i < n; i++) {
    scanf("%d%d%d", &x, &y, &z);
    e[x].push_back(make_pair(y, (long long)z)),
        e[y].push_back(make_pair(x, (long long)z));
  }
  sz[0] = mn[0] = n, getrt(1, 0), solve();
  printf("%I64d\n", ans * 2);
  for (int i = 1; i <= n; i++) printf("%d ", a[i]);
  return 0;
}
