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;
int N, cent;
vector<pair<int, signed long long> > E[100001];
signed long long num[100001];
signed long long sc1[100001], sc2[100001], msc;
int M[100001];
int snum[100001];
vector<vector<int> > SS;
set<int> idord;
map<int, set<int> > numord;
void dfs1(int cur, int pre) {
  int i;
  num[cur] = 1;
  for (i = 0; i < E[cur].size(); i++) {
    int tar = E[cur][i].first;
    if (tar != pre) {
      dfs1(tar, cur);
      sc1[cur] += sc1[tar] + num[tar] * E[cur][i].second;
      num[cur] += num[tar];
    }
  }
}
void dfs2(int cur, int pre, signed long long csc) {
  int i;
  for (i = 0; i < E[cur].size(); i++) {
    int tar = E[cur][i].first;
    if (tar != pre)
      dfs2(tar, cur,
           csc + sc1[cur] + (N - 2 * num[tar]) * E[cur][i].second - sc1[tar]);
  }
  signed long long mav = N - num[cur];
  for (i = 0; i < E[cur].size(); i++)
    if (E[cur][i].first != pre) mav = max(mav, num[E[cur][i].first]);
  if (mav <= N / 2 && csc + sc1[cur] > msc) msc = csc + sc1[cur], cent = cur;
}
void dfs3(int cur, int pre, int id) {
  int i;
  M[cur] = id;
  for (i = 0; i < E[cur].size(); i++)
    if (E[cur][i].first != pre) dfs3(E[cur][i].first, cur, id);
}
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N;
  for (i = 0; i < N - 1; i++) {
    cin >> x >> y >> j;
    E[x - 1].push_back(make_pair(y - 1, j));
    E[y - 1].push_back(make_pair(x - 1, j));
  }
  dfs1(0, -1);
  dfs2(0, -1, 0);
  (void)printf("%lld\n", 2 * msc);
  M[cent] = 0;
  for (i = 0; i < E[cent].size(); i++) dfs3(E[cent][i].first, cent, i + 1);
  SS.resize(E[cent].size() + 1);
  for (i = N - 1; i >= 0; i--) SS[M[i]].push_back(i);
  for (j = 0; j < SS.size(); j++)
    snum[j] = SS[j].size() * 2, idord.insert(SS[j].back()),
    numord[-snum[j]].insert(j);
  for (i = 0; i < N; i++) {
    j = M[i];
    numord[-snum[j]].erase(j);
    if (numord[-snum[j]].empty()) numord.erase(-snum[j]);
    snum[j]--;
    if (SS[j].size()) numord[-snum[j]].insert(j);
    if (-numord.begin()->first >= (N - i) &&
        *numord.begin()->second.begin() != 0)
      j = *numord.begin()->second.begin();
    else {
      for (__typeof(idord.begin()) it = idord.begin(); it != idord.end(); it++)
        if (M[*it] != j || j == 0) {
          j = M[*it];
          break;
        }
    }
    (void)printf("%d ", SS[j].back() + 1);
    numord[-snum[j]].erase(j);
    if (numord[-snum[j]].empty()) numord.erase(-snum[j]);
    idord.erase(SS[j].back());
    SS[j].pop_back();
    snum[j]--;
    if (SS[j].size()) idord.insert(SS[j].back()), numord[-snum[j]].insert(j);
  }
  (void)printf("\n");
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false);
  for (i = 0; i < argc - 1; i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < s.size(); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}
