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;
struct node1 {
  int e;
  long long w;
};
struct node_set {
  int e;
  int w;
  friend bool operator<(const node_set &a, const node_set &b) {
    return a.w < b.w;
  }
};
struct node_tre {
  int l;
  int r;
  int maxx;
  int s1;
  int s2;
} tre[400005];
int n;
int rt;
int siz[100005];
int bel[100005];
long long dep[100005];
vector<node1> g[100005];
long long ans;
set<int> in[100005];
set<node_set> minn;
void build(int l, int r, int k) {
  tre[k].l = l;
  tre[k].r = r;
  tre[k].maxx = tre[k].s1 = tre[k].s2 = 0;
  if (l == r) {
    tre[k].maxx = in[l].size() * 2;
    tre[k].s1 = in[l].size();
    tre[k].s2 = in[l].size();
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, k << 1);
  build(mid + 1, r, k << 1 | 1);
  tre[k].maxx = max(tre[k << 1].maxx, tre[k << 1 | 1].maxx);
  tre[k].s1 = tre[k << 1].s1 + tre[k << 1 | 1].s1;
  tre[k].s2 = tre[k << 1].s2 + tre[k << 1 | 1].s2;
}
void delet1(int u, int k) {
  if (tre[k].l > u || tre[k].r < u) return;
  if (tre[k].l == tre[k].r) {
    tre[k].s1--;
    tre[k].maxx = tre[k].s1 + tre[k].s2;
    return;
  }
  delet1(u, k << 1);
  delet1(u, k << 1 | 1);
  tre[k].maxx = max(tre[k << 1].maxx, tre[k << 1 | 1].maxx);
  tre[k].s1 = tre[k << 1].s1 + tre[k << 1 | 1].s1;
  tre[k].s2 = tre[k << 1].s2 + tre[k << 1 | 1].s2;
}
void delet2(int u, int k) {
  if (tre[k].l > u || tre[k].r < u) return;
  if (tre[k].l == tre[k].r) {
    tre[k].s2--;
    tre[k].maxx = tre[k].s1 + tre[k].s2;
    return;
  }
  delet2(u, k << 1);
  delet2(u, k << 1 | 1);
  tre[k].maxx = max(tre[k << 1].maxx, tre[k << 1 | 1].maxx);
  tre[k].s1 = tre[k << 1].s1 + tre[k << 1 | 1].s1;
  tre[k].s2 = tre[k << 1].s2 + tre[k << 1 | 1].s2;
}
int ask(int k, int fin) {
  if (tre[k].maxx != fin) return 0;
  if (tre[k].l == tre[k].r) return tre[k].l;
  int t = ask(k << 1, fin);
  if (t) return t;
  return ask(k << 1 | 1, fin);
}
void dfs_fouc(int u, int fa) {
  int maxx = -1;
  siz[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].e;
    if (v != fa) {
      dfs_fouc(v, u);
      siz[u] += siz[v];
      maxx = max(maxx, siz[v]);
    }
  }
  maxx = max(maxx, n - siz[u]);
  if (n / 2 >= maxx) rt = u;
}
void dfs_dep(int u, int fa) {
  ans += dep[u] * 2;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].e;
    if (v != fa) {
      dep[v] = dep[u] + g[u][i].w;
      dfs_dep(v, u);
    }
  }
}
void dfs_bel(int u, int fa, int _ind) {
  bel[u] = _ind;
  in[_ind].insert(u);
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].e;
    if (v != fa) dfs_bel(v, u, _ind);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    long long w;
    cin >> u >> v >> w;
    g[u].push_back((node1){v, w});
    g[v].push_back((node1){u, w});
  }
  dfs_fouc(1, 0);
  dfs_dep(rt, 0);
  for (int i = 0; i < g[rt].size(); i++) dfs_bel(g[rt][i].e, rt, i + 1);
  bel[rt] = g[rt].size() + 1;
  in[g[rt].size() + 1].insert(rt);
  for (int i = 1; i <= g[rt].size() + 1; i++) {
    set<int>::iterator it = in[i].begin();
    minn.insert((node_set){i, *it});
  }
  cout << ans << '\n';
  build(1, g[rt].size() + 1, 1);
  for (int i = 1; i <= n; i++) {
    int u = ask(1, tre[1].maxx);
    if (tre[1].maxx >= n - i + 1 && (bel[i] != u && u != g[rt].size() + 1)) {
      set<int>::iterator it = in[u].begin();
      int t = *it;
      cout << t << ' ';
      in[u].erase(in[u].find(t));
      minn.erase(minn.find((node_set){u, t}));
      delet1(u, 1);
      delet2(bel[i], 1);
      if (!in[u].empty()) {
        it = in[u].begin();
        minn.insert((node_set){u, *it});
      }
    } else {
      set<node_set>::iterator it1 = minn.begin();
      node_set t = *it1;
      if (t.e == bel[i] && t.w != rt) {
        minn.erase(it1);
        set<node_set>::iterator it2 = minn.begin();
        node_set t2 = *it2;
        minn.insert(t);
        t = t2;
      }
      cout << t.w << ' ';
      delet1(t.e, 1);
      delet2(bel[i], 1);
      minn.erase(minn.find(t));
      in[t.e].erase(in[t.e].find(t.w));
      if (!in[t.e].empty()) {
        set<int>::iterator it = in[t.e].begin();
        minn.insert((node_set){t.e, *it});
      }
    }
  }
  return 0;
}
