#include <bits/stdc++.h>
#define nMax 200005
#define INF 999999999
#define mp make_pair
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");


vector < pair < int , int > > G[nMax];

struct cmp{
    bool operator()(pair <int,int> x , pair <int,int> y){
        return x.second>y.second;}
        };

priority_queue < pair <int , int> , vector < pair < int, int > > , cmp> heap;

int viz[nMax], m, n, tata[nMax], nr, x, y, i, s, cost;
vector < int > d (nMax, INF);
int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i ++){
        f >> x >> y >> cost;
        G[x].push_back(mp(y, cost));
        G[y].push_back(mp(x,cost));
    }

    d[1] = 0;
    tata[1] = 0;
    viz[1] = 1;
    int nr = 1;


    for(auto v : G[1]){
        heap.push(v);
        d[v.first] = v.second;
        tata[v.first] = 1;
    }

    while(nr != n - 1 && (!heap.empty())){
        auto node = heap.top();
        heap.pop();
        if(viz[node.first] == 0){
            nr ++;
            viz[node.first] = 1;
            for(auto v : G[node.first]){
                if (viz[v.first] == 0){
                    if(d[v.first] > v.second){
                        d[v.first] = v.second;
                        tata[v.first] = node.first;
                        heap.push(v);
                    }
                }
            }
        }
    }

    for(i = 1; i <= n; i++)
        s += d[i];
    g << s << '\n' << n - 1<< '\n';
    for(i = 2 ;i <= n; i ++)
        g << i << " " << tata[i] << '\n';


    return 0;
}