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 N = 1e5 + 10;
const int INF = 1e9 + 19;
bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.first > b.first || (a.first == b.first && a.second < b.second);
}
int n;
vector<pair<int, int> > e[N];
int use[N];
int center;
long long answer;
vector<int> data;
int st[N];
int fn[N];
int tree[N * 4];
int rev[N];
set<pair<int, int>, bool (*)(pair<int, int>, pair<int, int>)> q(cmp);
int cnt[N];
int pos[N];
void read() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int v, u, c;
    scanf("%d%d%d", &v, &u, &c);
    v--;
    u--;
    e[v].push_back(make_pair(u, c));
    e[u].push_back(make_pair(v, c));
  }
}
int dfs0(int v) {
  use[v] = 1;
  int cnt = 0;
  int mx = 0;
  for (auto x : e[v]) {
    if (!use[x.first]) {
      int tmp = dfs0(x.first);
      mx = max(tmp, mx);
      cnt += tmp;
    }
  }
  mx = max(mx, n - 1 - cnt);
  if (mx * 2 <= n) {
    center = v;
  }
  return cnt + 1;
}
void dfs1(int v, long long h) {
  use[v] = 1;
  answer += h * 2;
  for (auto x : e[v])
    if (!use[x.first]) dfs1(x.first, h + x.second);
}
void dfs2(int v) {
  use[v] = 1;
  data.push_back(v);
  for (auto x : e[v])
    if (!use[x.first]) dfs2(x.first);
}
void build(int v, int ll, int rr) {
  if (ll + 1 == rr) {
    tree[v] = data[ll];
    return;
  }
  build(v * 2 + 1, ll, (ll + rr) / 2);
  build(v * 2 + 2, (ll + rr) / 2, rr);
  tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
}
int get(int v, int ll, int rr, int l, int r) {
  if (ll >= r || l >= rr) return INF;
  if (l <= ll && rr <= r) return tree[v];
  return min(get(v * 2 + 1, ll, (ll + rr) / 2, l, r),
             get(v * 2 + 2, (ll + rr) / 2, rr, l, r));
}
void setT(int v, int ll, int rr, int pos, int val) {
  if (pos < ll || rr <= pos) return;
  if (ll + 1 == rr) {
    tree[v] = val;
    return;
  }
  setT(v * 2 + 1, ll, (ll + rr) / 2, pos, val);
  setT(v * 2 + 2, (ll + rr) / 2, rr, pos, val);
  tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
}
pair<long long, vector<int> > solve() {
  answer = 0;
  q.clear();
  memset(use, 0, sizeof(use));
  center = -1;
  dfs0(0);
  assert(center != -1);
  memset(use, 0, sizeof(use));
  dfs1(center, 0);
  memset(use, 0, sizeof(use));
  vector<pair<vector<int>, int> > subTree;
  use[center] = 1;
  subTree.push_back(make_pair(vector<int>(1, center), center));
  for (auto x : e[center]) {
    data.clear();
    dfs2(x.first);
    subTree.push_back(make_pair(data, x.first));
  }
  int cur = 0;
  data.resize(n);
  for (auto& x : subTree) {
    st[x.second] = cur;
    cnt[x.second] = x.first.size();
    cur += cnt[x.second];
    fn[x.second] = cur;
    for (int i = 0; i < (int)x.first.size(); i++) {
      data[i + st[x.second]] = x.first[i];
      rev[x.first[i]] = x.second;
    }
    q.insert(make_pair(cnt[x.second] * 2, x.second));
  }
  assert(cur == n);
  for (int i = 0; i < n; i++) {
    pos[data[i]] = i;
    cnt[i] *= 2;
  }
  build(0, 0, n);
  vector<int> ans(n, -1);
  for (int i = 0; i < n; i++) {
    int all = n - i;
    int type = rev[i];
    int x;
    auto g = q.begin();
    if ((int)q.size() >= 2 && g->second == center) {
      auto it = q.begin();
      it++;
      if (it->first == g->first) g = it;
    }
    if (g->first == all && g->second != type && g->second != center) {
      x = get(0, 0, n, st[g->second], fn[g->second]);
    } else {
      if (i == center)
        x = get(0, 0, n, 0, n);
      else
        x = min(get(0, 0, n, 0, st[type]), get(0, 0, n, fn[type], n));
    }
    ans[i] = x;
    setT(0, 0, n, pos[x], INF);
    assert(q.count(make_pair(cnt[rev[i]], rev[i])) == 1);
    q.erase(make_pair(cnt[rev[i]], rev[i]));
    cnt[rev[i]]--;
    q.insert(make_pair(cnt[rev[i]], rev[i]));
    assert(q.count(make_pair(cnt[rev[x]], rev[x])) == 1);
    q.erase(make_pair(cnt[rev[x]], rev[x]));
    cnt[rev[x]]--;
    q.insert(make_pair(cnt[rev[x]], rev[x]));
  }
  return make_pair(answer, ans);
}
void printAns(pair<long long, vector<int> > ans) {
  cout << ans.first << "\n";
  for (auto x : ans.second) printf("%d ", x + 1);
  printf("\n");
}
void genTest() {
  n = 100000;
  for (int i = 0; i < n; i++) e[i].clear();
  vector<pair<int, int> > edges;
  for (int i = 1; i < n; i++) {
    int v = rand() % i;
    edges.push_back(make_pair(v, i));
  }
  vector<int> per(n);
  for (int i = 0; i < n; i++) per[i] = i;
  random_shuffle(per.begin(), per.end());
  for (auto x : edges) {
    e[per[x.first]].push_back(make_pair(per[x.second], 1));
    e[per[x.second]].push_back(make_pair(per[x.first], 1));
  }
}
void printTest() {
  cerr << n << endl;
  for (int v = 0; v < n; v++)
    for (auto x : e[v])
      if (x.first < v) cout << v + 1 << " " << x.first + 1 << " " << 1 << endl;
}
pair<long long, vector<int> > stupid() {
  vector<vector<int> > dist(n, vector<int>(n, INF));
  for (int v = 0; v < n; v++)
    for (auto x : e[v]) dist[v][x.first] = x.second;
  for (int i = 0; i < n; i++) dist[i][i] = 0;
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
  int fact = 1;
  for (int i = 0; i < n; i++) fact *= (i + 1);
  vector<int> per;
  for (int i = 0; i < n; i++) per.push_back(i);
  pair<long long, vector<int> > answer = make_pair(-1, vector<int>());
  for (int tt = 0; tt < fact; tt++) {
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += dist[i][per[i]];
    if (sum > answer.first || (sum == answer.first && per < answer.second))
      answer = make_pair(sum, per);
    next_permutation(per.begin(), per.end());
  }
  return answer;
}
void pr(pair<long long, vector<int> > data) {
  cerr << data.first << "   :   ";
  for (auto x : data.second) cerr << x << " ";
  cerr << endl;
}
void stress() {
  for (int tt = 0;; tt++) {
    cerr << "test: " << tt << endl;
    genTest();
    auto r1 = solve();
  }
}
int main() {
  if (1) {
    int k = 1;
    for (int tt = 0; tt < k; tt++) {
      read();
      printAns(solve());
    }
  } else {
    stress();
  }
  return 0;
}
