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 maxn = 100010;
const int inf = 1000000000;
int n;
int sz[maxn], bigg[maxn];
vector<pair<int, int>> graph[maxn];
void dfs(int t, int pa) {
  sz[t] = 1;
  bigg[t] = 0;
  for (auto x : graph[t])
    if (x.first != pa) {
      dfs(x.first, t);
      sz[t] += sz[x.first];
      bigg[t] = max(bigg[t], sz[x.first]);
    }
}
int find_center() {
  dfs(0, -1);
  for (int i = 0; i < n; i++)
    if (max(bigg[i], n - sz[i]) * 2 <= n) return i;
  return 0;
}
long long dep(int t, int pa, long long pre) {
  long long res = pre;
  for (auto x : graph[t])
    if (x.first != pa) {
      res += dep(x.first, t, pre + x.second);
    }
  return res;
}
int tot;
int p[maxn];
int pos[maxn];
int lo[maxn], hi[maxn];
vector<int> a;
void dfss(int t, int pa) {
  pos[t] = a.size();
  a.push_back(t);
  p[t] = tot;
  sz[tot]++;
  for (auto x : graph[t])
    if (x.first != pa) dfss(x.first, t);
}
struct Tree {
  int l, r, key;
  Tree *lc, *rc;
  Tree(int _l, int _r) : l(_l), r(_r) {
    if (l + 1 == r)
      key = a[l];
    else {
      lc = new Tree(l, (l + r) >> 1);
      rc = new Tree((l + r) >> 1, r);
      key = min(lc->key, rc->key);
    }
  }
  void remove(int x) {
    if (l + 1 == r)
      key = inf;
    else {
      x < (l + r) >> 1 ? lc->remove(x) : rc->remove(x);
      key = min(lc->key, rc->key);
    }
  }
  int query(int ll, int rr) {
    if (ll <= l && rr >= r) return key;
    int res = inf;
    if (ll < (l + r) >> 1) res = min(res, lc->query(ll, rr));
    if (rr > (l + r) >> 1) res = min(res, rc->query(ll, rr));
    return res;
  }
} * root;
set<pair<int, int>, greater<pair<int, int>>> S;
void kick(int id, int flag) {
  int k = p[id];
  S.erase(make_pair(sz[k], k));
  sz[k]--;
  S.insert(make_pair(sz[k], k));
  if (flag) root->remove(pos[id]);
}
int main() {
  int u, v, w;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    cin >> u >> v >> w;
    u--;
    v--;
    graph[u].push_back(make_pair(v, w));
    graph[v].push_back(make_pair(u, w));
  }
  int center = find_center();
  cout << dep(center, -1, 0) * 2 << endl;
  tot = 0;
  memset(sz, 0, sizeof(sz));
  lo[tot] = a.size();
  pos[center] = a.size();
  a.push_back(center);
  p[center] = tot;
  sz[tot] = -1;
  hi[tot++] = a.size();
  for (auto x : graph[center]) {
    lo[tot] = a.size();
    dfss(x.first, center);
    hi[tot++] = a.size();
  }
  root = new Tree(0, n);
  for (int i = 0; i < tot; i++) sz[i] *= 2;
  for (int i = 0; i < tot; i++) S.insert(make_pair(sz[i], i));
  for (int i = 0; i < n; i++) {
    pair<int, int> cnt = *S.begin();
    if (n - i == cnt.first && p[i] != cnt.second) {
      int id = root->query(lo[cnt.second], hi[cnt.second]);
      cout << id + 1 << ' ';
      kick(id, 1);
      kick(i, 0);
    } else {
      int L = lo[p[i]], R = hi[p[i]];
      if (i == center) L = R = 0;
      int id = inf;
      if (L > 0) id = min(id, root->query(0, L));
      if (R < n) id = min(id, root->query(R, n));
      cout << id + 1 << ' ';
      kick(id, 1);
      kick(i, 0);
    }
  }
  cout << endl;
  return 0;
}
