import javafx.util.Pair;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Prim {

    int n;
    LinkedList<Pair<Integer, Integer>> incList[];


    private Prim(int n){
        this.n = n;
        incList = new LinkedList[n];

        for (int i = 0; i < n; i++){
            incList[i] = new LinkedList<>();
        }
    }

    private void addEdge(int a, int b, int len){
        Pair p1 = new Pair<>(b, len);
        Pair p2 = new Pair<>(a, len);
        incList[a].add(p1);
        incList[b].add(p2);
    }



    private void findShortestDist(){
        int[] minDist = new int[n];
        Arrays.fill(minDist, 100000000);
        int[] next  = new int[n];
        Arrays.fill(next, -1);
        boolean[] used = new boolean[n];

        /*minDist[0] = 0;

        for (int i = 0; i < n; i++) {
            int v = -1;
            for (int j = 0; j < n; j++) {
                if (!used[j] && (v == -1 || minDist[j] < minDist[v])) {
                    v = j;
                }
            }
            used[v] = true;
            for (int j = 0; j < incList[v].size(); j++) {
                if (incList[v].get(j).getValue() < minDist[j]) {
                    minDist[j] = incList[v].get(j).getValue();
                    next[j] = v;
                }
            }
        }*/



        PriorityQueue<Para> q = new PriorityQueue<Para>();

        q.add(new Para(0, 0));

        for (int i = 0; i < n; i++){


            int v = q.peek().getKey();
            q.remove(q.peek());

            for (int j = 0; j < incList[v].size(); j++){
                int to = incList[v].get(j).getKey();
                int len = incList[v].get(j).getValue();
                if (len < minDist[to]){
                    q.remove(new Para (to, minDist[to]));
                    minDist[to] = len;
                    next[to] = v;
                    q.add(new Para (to, minDist[to]));
                }
            }
        }



        int ans = 0;
        for (int i = 0; i < n; i++){
            System.out.print(next[i] + " ");
        }
        System.out.println(" ");
        for (int i =0 ; i < n - 1; i++) {
            System.out.print(minDist[i]     + " ");
            ans += minDist[i];
        }
        System.out.println(ans);
    }


    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        Prim graph = new Prim(n);

        for (int i = 0; i < m; i++){
            graph.addEdge(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        graph.findShortestDist();
    }

}