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 long double pi = 3.14159265359;
template <typename T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
void chmin(T &x, T y) {
  x = min(x, y);
}
template <typename T>
void chmax(T &x, T y) {
  x = max(x, y);
}
template <typename U, typename V>
ostream &operator<<(ostream &s, const pair<U, V> &x) {
  s << "(" << x.first << ", " << x.second << ")";
  return s;
}
template <typename U>
ostream &operator<<(ostream &s, const vector<U> &x) {
  s << "[";
  bool was = false;
  for (auto it : x) {
    if (was) {
      s << ", ";
    }
    was = true;
    s << it;
  }
  s << "]";
  return s;
}
const int maxn = 1e5 + 5;
const int inf = 1e9;
vector<pair<int, int>> g[maxn];
pair<int, vector<int>> bst(1e9, {});
int n;
long long cost = 0;
int dfs(int v, int p = -1) {
  int sz = 1;
  for (auto to : g[v]) {
    if (to.first == p) {
      continue;
    }
    int c = dfs(to.first, v);
    sz += c;
    cost += to.second * 2LL * min(c, n - c);
    if (c == n - c) {
      chmin(bst, make_pair(0, vector<int>({v, to.first})));
    } else {
      chmin(bst, make_pair(abs(c - (n - c)),
                           vector<int>({c > n - c ? to.first : v})));
    }
  }
  return sz;
}
vector<int> comp;
void dfs2(int v, int pr) {
  comp.push_back(v);
  for (auto to : g[v]) {
    if (to.first != pr) {
      dfs2(to.first, v);
    }
  }
}
pair<int, int> t[maxn * 4];
void modify(int v, int l, int r, int i, int val) {
  if (l == r) {
    t[v] = make_pair(val, l);
    return;
  }
  int c = (l + r) >> 1;
  if (i <= c) {
    modify(2 * v, l, c, i, val);
  } else {
    modify(2 * v + 1, c + 1, r, i, val);
  }
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
pair<int, int> get(int v, int l, int r, int i, int j) {
  if (i <= l && r <= j) {
    return t[v];
  }
  pair<int, int> res(inf, 0);
  int c = (l + r) >> 1;
  if (i <= c) {
    chmin(res, get(2 * v, l, c, i, j));
  }
  if (c < j) {
    chmin(res, get(2 * v + 1, c + 1, r, i, j));
  }
  return res;
}
int main() {
  srand(time(NULL));
retry:
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    u = i + 2;
    v = rand() % (i + 1) + 1;
    w = 1;
    scanf("%d %d %d", &u, &v, &w);
    g[u].push_back(make_pair(v, w));
    g[v].push_back(make_pair(u, w));
  }
  if (n == 1) {
    cout << 0 << endl;
    cout << 1 << endl;
    return 0;
  }
  dfs(1);
  fill(t, t + maxn * 4, make_pair(inf, 0));
  vector<int> ci(n + 1, -1);
  vector<int> cl, cr;
  vector<int> cs;
  int sz = 0;
  int cz = 1;
  set<pair<int, int>> s;
  if (bst.second.size() == 2) {
    for (int i = 0; i < 2; i++) {
      comp.clear();
      dfs2(bst.second[i], bst.second[1 - i]);
      cl.push_back(cz), cr.push_back(cz + comp.size() - 1);
      cs.push_back(comp.size() * 2);
      for (int x : comp) {
        ci[x] = sz;
        modify(1, 0, maxn - 1, cz++, x);
      }
      s.insert(make_pair(comp.size() * 2, sz));
      sz++;
    }
  } else {
    for (auto to : g[bst.second[0]]) {
      comp.clear();
      dfs2(to.first, bst.second[0]);
      cl.push_back(cz), cr.push_back(cz + comp.size() - 1);
      cs.push_back(comp.size() * 2);
      for (int x : comp) {
        ci[x] = sz;
        modify(1, 0, maxn - 1, cz++, x);
      }
      s.insert(make_pair(comp.size() * 2, sz));
      sz++;
    }
    modify(1, 0, maxn - 1, cz++, bst.second[0]);
  }
  vector<int> ans(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    int big = s.empty() ? 0 : s.rbegin()->first;
    int bigI = s.empty() ? -1 : s.rbegin()->second;
    if (ci[i] == bigI || big <= n - i) {
      if (ci[i] == -1) {
        auto r = get(1, 0, maxn - 1, 0, maxn - 1);
        assert(r.first != inf);
        ans[i] = r.first;
        modify(1, 0, maxn - 1, r.second, inf);
        if (ci[r.first] != -1) {
          s.erase(make_pair(cs[ci[r.first]], ci[r.first]));
          cs[ci[r.first]]--;
          s.insert(make_pair(cs[ci[r.first]], ci[r.first]));
        }
      } else {
        pair<int, int> r(inf, 0);
        if (0 <= cl[ci[i]] - 1) {
          chmin(r, get(1, 0, maxn - 1, 0, cl[ci[i]] - 1));
        }
        chmin(r, get(1, 0, maxn - 1, cr[ci[i]] + 1, maxn - 1));
        assert(r.first != inf);
        ans[i] = r.first;
        modify(1, 0, maxn - 1, r.second, inf);
        if (ci[i] != -1) {
          s.erase(make_pair(cs[ci[i]], ci[i]));
          cs[ci[i]]--;
          s.insert(make_pair(cs[ci[i]], ci[i]));
        }
        if (ci[r.first] != -1) {
          s.erase(make_pair(cs[ci[r.first]], ci[r.first]));
          cs[ci[r.first]]--;
          s.insert(make_pair(cs[ci[r.first]], ci[r.first]));
        }
      }
    } else {
      auto r = get(1, 0, maxn - 1, cl[bigI], cr[bigI]);
      assert(r.first != inf);
      ans[i] = r.first;
      modify(1, 0, maxn - 1, r.second, inf);
      if (ci[i] != -1) {
        s.erase(make_pair(cs[ci[i]], ci[i]));
        cs[ci[i]]--;
        s.insert(make_pair(cs[ci[i]], ci[i]));
      }
      if (ci[r.first] != -1) {
        s.erase(make_pair(cs[ci[r.first]], ci[r.first]));
        cs[ci[r.first]]--;
        s.insert(make_pair(cs[ci[r.first]], ci[r.first]));
      }
    }
  }
  cout << cost << endl;
  for (int i = 1; i <= n; i++) {
    if (i > 1) {
      printf(" ");
    }
    printf("%d", ans[i]);
  }
  return 0;
}
