#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_set>
#include <set>

int n,mo;
struct pair
{
    int x,y;
};

struct triple
{
    int x,y,z;
};

std::vector<pair> m[200001];

std::vector<pair> sg;//subgraph
std::unordered_set<int> vn;//visited nodes

struct classcomp{
    bool operator() (triple a,triple b)
    {
        if(a.y<b.y)return 1;
        if(a.y>b.y)return 0;
        if(a.x>b.x)return 1;
        if(a.x<b.x)return 0;
        if(a.z<b.z)return 1;
        return 0;
    }
    };

std::set<triple,classcomp> cn;//candidate nodes and associated costs and source nodes

void add(int dest,int cost,int source)
{
    triple a;
    a.x=dest;
    a.y=cost;
    a.z=source;
    cn.insert(a);
}

void printcn()
{
    for(std::set<triple>::iterator it=cn.begin();it!=cn.end();it++)
        std::cout<<"(dest = "<<(*it).x<<", cost = "<<(*it).y<<", source = "<<(*it).z<<") ";
    std::cout<<'\n';
}

void printal(int node)
{
    for(int i=0;i<m[node].size();i++)
            std::cout<<"( "<<m[node][i].x<<", "<<(vn.find(m[node][i].x)==vn.end())<<")  ";
    std::cout<<'\n';
}

int main()
{
    std::fstream fin("apm.in",std::ios::in),fout("apm.out",std::ios::out);
    fin>>n>>mo;
    int s=0;
    for(int i=0;i<mo;i++)
    {
        int a,b,c;
        pair p;
        fin>>a>>b>>c;
        p.x=b;
        p.y=c;
        m[a].push_back(p);
        p.x=a;
        m[b].push_back(p);
    }

    vn.insert(1);
    for(int i=0;i<m[1].size();i++)
        if(vn.find(m[1][i].x)==vn.end())
            add(m[1][i].x,m[1][i].y,1);
    while(vn.size()<n)
    {
        //printcn();std::cout<<'\n';
        int node=(*cn.begin()).x;
        int source=(*cn.begin()).z;
        int cost=(*cn.begin()).y;
        cn.erase(cn.begin());

        if(vn.find(node)!=vn.end())continue;
        s+=cost;
        vn.insert(node);
        //printal(node);
        //std::cout<<"\n\n";
        for(int i=0;i<m[node].size();i++)
            if(vn.find(m[node][i].x)==vn.end())
                add(m[node][i].x,m[node][i].y,node);
        pair a;
        a.x=node;
        a.y=source;
        sg.push_back(a);
    }

    fout<<s<<'\n'<<n-1<<'\n';
    for(int i=0;i<sg.size();i++)fout<<sg[i].x<<' '<<sg[i].y<<'\n';
}