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 inf = (int)1.01e9;
const long long infll = (long long)1.01e18;
const long double eps = 1e-9;
const long double pi = acos((long double)-1);
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
void precalc() {}
const int maxn = (int)1e5 + 5;
int n;
vector<pair<int, int>> g[maxn];
bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    int v, u, w;
    scanf("%d%d%d", &v, &u, &w);
    v--;
    u--;
    g[v].push_back(make_pair(u, w));
    g[u].push_back(make_pair(v, w));
  }
  return true;
}
long long res;
int ts[maxn];
void dfs(int v, int p, int pw) {
  ts[v] = 1;
  for (int i = 0; i < ((int)(g[v]).size()); i++) {
    int u = g[v][i].first, w = g[v][i].second;
    if (u == p) {
      continue;
    }
    dfs(u, v, w);
    ts[v] += ts[u];
  }
  if (p != -1) {
    res += (long long)pw * min(ts[v], n - ts[v]);
  }
}
void dfs1(int v, int p, vector<int> &vs) {
  vs.push_back(v);
  for (int i = 0; i < ((int)(g[v]).size()); i++) {
    int u = g[v][i].first;
    if (u == p) {
      continue;
    }
    dfs1(u, v, vs);
  }
}
int cnt[maxn];
int c[maxn];
vector<vector<int>> vs;
set<pair<int, int>> mns;
set<pair<int, int>, greater<pair<int, int>>> st;
int ans[maxn];
void solve() {
  res = 0;
  dfs(0, -1, -1);
  res *= 2;
  printf("%lld\n", res);
  if (n == 1) {
    printf("%d\n", 1);
    return;
  }
  if (n == 2) {
    printf("%d %d\n", 2, 1);
    return;
  }
  int v = 0;
  int p = -1;
  while (true) {
    int nv = -1;
    for (int i = 0; i < ((int)(g[v]).size()); i++) {
      int u = g[v][i].first;
      if (u == p) {
        continue;
      }
      if (2 * ts[u] > n) {
        nv = u;
        break;
      }
    }
    if (nv == -1) {
      break;
    }
    p = v;
    v = nv;
  }
  vs.clear();
  mns.clear();
  st.clear();
  for (int i = 0; i < ((int)(g[v]).size()); i++) {
    int u = g[v][i].first;
    vs.push_back({});
    dfs1(u, v, vs.back());
    sort(vs.back().begin(), vs.back().end(), greater<int>());
    for (int j = 0; j < ((int)(vs.back()).size()); j++) {
      int w = vs.back()[j];
      c[w] = i;
    }
    cnt[i] = ((int)(vs.back()).size()) * 2;
    mns.insert(make_pair(vs.back().back(), i));
    st.insert(make_pair(cnt[i], i));
  }
  vs.push_back({v});
  c[v] = ((int)(vs).size()) - 1;
  cnt[((int)(vs).size()) - 1] = 2;
  mns.insert(make_pair(vs.back().back(), ((int)(vs).size()) - 1));
  st.insert(make_pair(cnt[((int)(vs).size()) - 1], ((int)(vs).size()) - 1));
  vector<int> big;
  for (int i = 0; i < n; i++) {
    int a = c[i], b = -1;
    if (cnt[a] == n - i) {
      auto it = mns.begin();
      if (i != v && it->second == a) {
        it++;
      }
      b = it->second;
    } else {
      big.clear();
      for (auto it = st.begin(); it != st.end(); it++) {
        if (it->first < n - i) {
          break;
        }
        if (it->second != ((int)(vs).size()) - 1) {
          big.push_back(it->second);
        }
      }
      if (big.empty()) {
        auto it = mns.begin();
        if (i != v && it->second == a) {
          it++;
        }
        b = it->second;
      } else {
        b = big[0];
      }
    }
    mns.erase(make_pair(vs[b].back(), b));
    st.erase(make_pair(cnt[a], a));
    st.erase(make_pair(cnt[b], b));
    ans[i] = vs[b].back();
    vs[b].pop_back();
    cnt[a]--;
    cnt[b]--;
    if (!vs[b].empty()) {
      mns.insert(make_pair(vs[b].back(), b));
    }
    st.insert(make_pair(cnt[a], a));
    st.insert(make_pair(cnt[b], b));
  }
  for (int i = 0; i < n; i++) {
    printf("%d ", ans[i] + 1);
  }
  printf("\n");
}
int main() {
  precalc();
  while (read()) {
    solve();
  }
  return 0;
}
