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 root, n, tot, size[110000], at[110000], as[110000];
long long ans;
int per[110000], pos[110000], zz[110000], in, vp[110000], ms[110000];
struct pp {
  int id, r;
  long long w;
  bool operator<(const pp &temp) const { return id < temp.id; }
};
vector<pp> adj[110000], anc[110000];
vector<pp>::iterator ie;
pp now;
set<pp> an[110000];
set<pp>::iterator iee;
bool vis[110000];
struct qq {
  int id, size;
  bool operator<(const qq &temp) const {
    if (size == temp.size) return id < temp.id;
    return size > temp.size;
  }
};
set<qq> hs;
qq th, hp;
set<qq>::iterator it;
set<int> ls;
set<int>::iterator itt;
void dfs(int id1, int id2) {
  int siz, id, i, j, s, p, q;
  size[id1] = 1;
  siz = adj[id1].size();
  for (i = 0; i < siz; i++) {
    id = adj[id1][i].id;
    if (id == id2) continue;
    dfs(id, id1);
    size[id1] += size[id];
  }
}
void find_root(int id1, int id2) {
  int sp = 0, ax = 0, i, j, s, p, q, id, siz;
  siz = adj[id1].size();
  for (i = 0; i < siz; i++) {
    id = adj[id1][i].id;
    if (id == id2) continue;
    if (ax < size[id]) ax = size[id];
    find_root(id, id1);
  }
  if (ax < n - size[id1]) ax = n - size[id1];
  if (in > ax) {
    in = ax;
    root = id1;
  }
}
void solve(int id1, int id2, int pos, long long value) {
  int i, j, s, p, q, id, ip, siz, ax = 0, ht, ns, vn, nk;
  siz = adj[id1].size();
  if (id1 != root) {
    now.id = id1;
    now.w = value;
    anc[pos].push_back(now);
  }
  for (i = 0; i < siz; i++) {
    id = adj[id1][i].id;
    if (id == id2) continue;
    if (id1 == root) pos = i;
    solve(id, id1, pos, value + adj[id1][i].w);
  }
  if (id1 == root) {
    ans = 0;
    ls.clear();
    for (i = 0; i < n; i++) ls.insert(i);
    for (i = 0; i < siz; i++) {
      if (ax < anc[i].size()) {
        ax = anc[i].size();
        id = i;
      }
      for (j = 0; j < anc[i].size(); j++) ans += 2 * anc[i][j].w;
    }
    for (i = 0; i < siz; i++) {
      sort(anc[i].begin(), anc[i].end());
      an[i].clear();
    }
    hs.clear();
    for (i = 0; i < siz; i++) {
      int ts = anc[i].size();
      anc[i][ts - 1].r = anc[i][ts - 1].id + 1;
      for (j = ts - 2; j >= 0; j--) {
        if (anc[i][j].id == anc[i][j + 1].id - 1)
          anc[i][j].r = anc[i][j + 1].r;
        else
          anc[i][j].r = anc[i][j].id + 1;
      }
      for (j = 0; j < ts; j++) {
        an[i].insert(anc[i][j]);
        at[anc[i][j].id] = i;
        as[anc[i][j].id] = j;
      }
      th.id = i;
      th.size = ts * 2;
      zz[i] = ts * 2;
      hs.insert(th);
    }
    bool no = false;
    if (anc[id].size() == n - 1 - anc[id].size()) no = true;
    ht = 0;
    ns = 2 * n;
    int nh, nq;
    for (i = 0; i < n; i++) {
      itt = ls.lower_bound(ht);
      ht = *itt;
      nh = ht;
      nq = ns - 2;
      bool must = false;
      int must_id;
      if (i == root) {
        while (nh < n) {
          if (vis[nh] || (at[i] >= 0 && at[nh] == at[i])) {
            if (at[i] >= 0 && at[nh] == at[i]) {
              id = at[nh];
              ip = as[nh];
              nh = max(anc[id][ip].r, vp[at[i]]);
              vp[at[i]] = max(vp[at[i]], nh);
            }
            if (vis[nh]) {
              itt = ls.lower_bound(nh);
              nh = *itt;
            }
          } else if (nh == root) {
            it = hs.begin();
            if (nq - (it->size) >= (it->size)) break;
            nh++;
          } else {
            id = at[nh];
            ip = as[nh];
            it = hs.begin();
            th = *it;
            vn = 0;
            while (it != hs.end() && (at[nh] == it->id || at[i] == it->id)) {
              nk = it->size;
              if (at[nh] == it->id) nk--;
              if (at[i] == it->id) nk--;
              if (vn < nk) {
                vn = nk;
                hp = *it;
              }
              it++;
            }
            if (it != hs.end()) {
              if (vn < it->size) {
                vn = it->size;
                hp = *it;
              }
            }
            th = hp;
            if (nq - vn >= vn) break;
            nh = max(anc[id][ip].r, vp[id]);
          }
        }
      } else {
        it = hs.begin();
        if (it != hs.end()) {
          if (ns - 1 - (it->size) == it->size && at[i] != it->id) {
            must = true;
            nh = anc[it->id][0].id;
            must_id = it->id;
          } else {
            it++;
            if (it != hs.end()) {
              if (ns - 1 - (it->size) == it->size && at[i] != it->id &&
                  must_id > it->id) {
                must = true;
                nh = anc[it->id][0].id;
                must_id = it->id;
              }
            }
          }
        }
        if (must) nh = max(nh, ms[must_id]);
        nq = ns - 2;
        bool fir = true;
        int times = 0;
        while (nh < n) {
          if (must) {
            now.id = nh;
            iee = an[must_id].lower_bound(now);
            nh = iee->id;
          }
          id = at[nh];
          ip = as[nh];
          if (vis[nh] || at[nh] == at[i] || (must && must_id != at[nh])) {
            if (at[nh] == at[i]) nh = max(anc[id][ip].r, vp[at[nh]]);
            if (vis[nh]) {
              itt = ls.lower_bound(nh);
              nh = *itt;
              if (at[nh] >= 0) vp[at[nh]] = max(vp[at[nh]], nh);
              if (must) {
                id = must_id;
                now.id = nh;
                ie = lower_bound(anc[id].begin(), anc[id].end(), now);
                nh = ie->id;
              }
              now.id = nh;
            }
          } else {
            it = hs.begin();
            vn = 0;
            while (it != hs.end() && (it->id == at[i] || it->id == at[nh])) {
              nk = it->size;
              if (at[i] == it->id) nk--;
              if (at[nh] == it->id) nk--;
              if (vn < nk) {
                vn = nk;
                th = *it;
              }
              it++;
            }
            if (it != hs.end()) {
              nk = it->size;
              if (vn < nk) {
                vn = nk;
                th = *it;
              }
            }
            if (nq - vn >= vn) break;
            if (nh == root)
              nh++;
            else {
              nh = max(anc[id][ip].r, vp[id]);
              vp[id] = max(vp[id], nh);
            }
          }
        }
      }
      id = at[i];
      if (id >= 0) {
        th.id = id;
        th.size = zz[id];
        hs.erase(th);
        zz[id]--;
        th.size--;
        if (th.size > 0) hs.insert(th);
        vp[id] = nh + 1;
      }
      id = at[nh];
      if (id >= 0) {
        th.id = id;
        th.size = zz[id];
        hs.erase(th);
        zz[id]--;
        th.size--;
        if (th.size > 0) hs.insert(th);
      }
      ns = nq;
      per[i] = nh;
      ls.erase(nh);
      vis[nh] = true;
      id = at[nh];
      if (id >= 0) {
        now.id = nh;
        an[id].erase(now);
      }
      itt = ls.lower_bound(nh);
      if (siz < 100) {
        for (j = 0; j < siz; j++) vp[j] = max(vp[j], *itt);
      }
    }
  }
}
int main() {
  int u, v, w, i, j, s, p, q;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    adj[i].clear();
    anc[i].clear();
  }
  for (i = 0; i < n - 1; i++) {
    scanf("%d%d%d", &u, &v, &w);
    u--;
    v--;
    now.id = v;
    now.w = w;
    adj[u].push_back(now);
    now.id = u;
    adj[v].push_back(now);
  }
  dfs(0, -1);
  root = -1;
  in = 1000000000;
  find_root(0, -1);
  memset(at, -1, sizeof(at));
  memset(vis, false, sizeof(vis));
  memset(ms, 0, sizeof(ms));
  memset(vp, 0, sizeof(vp));
  solve(root, -1, -1, 0);
  printf("%I64d\n", ans);
  for (i = 0; i < n; i++) {
    if (i) putchar(' ');
    printf("%d", per[i] + 1);
  }
  printf("\n");
  return 0;
}
