#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 2;
const int inf = 2e9;
int n, m;

struct Edge {
    int from;
    int to;
    int cost;
};

 struct cmp{
    bool operator ()(Edge a, Edge b) {
        return a.cost > b.cost;
    }
 };

vector < vector <pair <int, int> > > graf(N);
vector < pair <int, int> > arb;
priority_queue < Edge, vector < Edge >, cmp > que;
bool viz[N];

void print(int s){
    printf("%d\n%d\n", s, n-1);

    for (int i=1; i<n; i++){
        printf("%d %d\n", arb[i].first, arb[i].second);
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int a, b, c;
    for (int i=0; i<m; i++){
        scanf("%d %d %d", &a, &b, &c);
        graf[a].push_back({b, c});
        graf[b].push_back({a, c});
    }



    int node, sum = 0;
    que.push({1, 1, 0});

    for (int i=1; i<=n; i++)
    {
        while (viz[que.top().to])
            que.pop();

        node = que.top().to;
        sum += que.top().cost;
        arb.push_back({que.top().from, que.top().to});
        que.pop();

        viz[node] = true;

        printf("%d ", node);
        for (auto j : graf[node]){
            if (!viz[j.first])
                que.push({node, j.first, j.second});
        }
    }

    print(sum);
}