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 = 2e5;
int N;
vector<pair<int, long long>> adj[MAXN];
int sz[MAXN];
int par[MAXN];
long long res;
int P[MAXN];
void dfs(int cur, int prv = -1, int pr = -1) {
  sz[cur] = 1;
  par[cur] = pr;
  for (auto i : adj[cur]) {
    int nxt = i.first;
    if (nxt == prv) continue;
    dfs(nxt, cur, (pr == -1) ? nxt : pr);
    res += sz[nxt] * i.second * 2;
    sz[cur] += sz[nxt];
  }
}
queue<int> trees[MAXN];
int deg[MAXN];
void go(int r) {
  cerr << r << '\n';
  dfs(r);
  par[r] = r;
  for (int i = 0; i < N; i++) {
    trees[par[i]].push(i);
  }
  for (int i = 0; i < N; i++) {
    deg[i] = trees[i].size() * 2;
  }
  assert(deg[r] == 2);
  deg[r]--;
  priority_queue<pair<int, int>> degs;
  for (int i = 0; i < N; i++) {
    if (deg[i]) degs.push(pair<int, int>(deg[i], i));
  }
  memset(P, -1, sizeof(P));
  priority_queue<int, vector<int>, greater<int>> vert;
  for (int i = 0; i < N; i++) {
    if (trees[i].size()) vert.push(trees[i].front());
  }
  for (int i = 0; i < N; i++) {
    int p = par[i];
    while (!degs.empty() && degs.top().first != deg[degs.top().second]) {
      int v = degs.top().second;
      degs.pop();
      degs.push(pair<int, int>(deg[v], v));
    }
    while (!vert.empty() && vert.top() != trees[par[vert.top()]].front()) {
      int v = par[vert.top()];
      vert.pop();
      if (!trees[v].empty()) vert.push(trees[v].front());
    }
    if (!degs.empty() && degs.top().first == N - i) {
      if (N - i == 1 && degs.top().second == r) {
        P[r] = r;
        break;
      }
      if (degs.top().second != p) {
        int q = degs.top().second;
        P[i] = trees[q].front();
        trees[q].pop();
        deg[p]--;
        deg[q]--;
        continue;
      }
    }
    assert(!vert.empty());
    if (i == r && vert.top() == r) {
      P[i] = r;
      trees[r].pop();
      deg[r]--;
      deg[r]--;
      continue;
    }
    bool vtop = par[vert.top()] == p;
    if (vtop) vert.pop();
    while (!vert.empty() && vert.top() != trees[par[vert.top()]].front()) {
      int v = par[vert.top()];
      vert.pop();
      if (!trees[v].empty()) vert.push(trees[v].front());
    }
    P[i] = vert.top();
    assert(trees[par[vert.top()]].front() == vert.top());
    trees[par[vert.top()]].pop();
    deg[p]--;
    deg[par[vert.top()]]--;
    if (vtop) {
      vert.push(trees[p].front());
    }
  }
}
void gosplit(int l, int r) {
  cerr << l << ' ' << r << '\n';
  go(l);
}
bool findcenter(int cur, int prv = -1) {
  sz[cur] = 1;
  int msize = 0;
  for (auto i : adj[cur]) {
    int nxt = i.first;
    if (nxt == prv) continue;
    if (findcenter(nxt, cur)) return true;
    sz[cur] += sz[nxt];
    if (sz[nxt] * 2 == N) {
      gosplit(cur, nxt);
      return true;
    }
    msize = max(sz[nxt], msize);
  }
  if (msize * 2 < N && (N - sz[cur]) * 2 < N) {
    go(cur);
    return true;
  }
  return false;
}
int main() {
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    adj[u].push_back(pair<int, long long>(v, w));
    adj[v].push_back(pair<int, long long>(u, w));
  }
  findcenter(0);
  cout << res << '\n';
  for (int i = 0; i < N; i++) cout << P[i] + 1 << ' ';
  cout << '\n';
}
