#include <fstream>
#include <vector>
#include <set>
const int NMAX=200005;

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct edge
{
    int a, b, c;
    bool operator<(const edge& other) const
    {
        if(c==other.c)
        {
            if(b==other.b)
                return a<other.a;
            return b<other.b;
        }
        return c<other.c;
    }
};

void mst();
int find(int);
bool unite(int, int);

int n, m;
vector <pair<int, int>> v[NMAX], ans;
set <edge> s;
bool in[NMAX];

int main()
{
    int i, a, b, c;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    mst();
    return 0;
}

void mst()
{
    int cost=0;
    edge p;
    in[1]=true;
    for(auto i:v[1])
    {
        s.insert({1, i.first, i.second});
    }
    while(!s.empty())
    {
        p=*s.begin();
        s.erase(s.begin());
        if(!in[p.b])
        {
            in[p.b]=true;
            cost+=p.c;
            ans.push_back({p.a, p.b});
            for(auto i:v[p.b])
            {
                s.insert({p.b, i.first, i.second});
            }
        }
    }
    fout<<cost<<'\n';
    fout<<ans.size()<<'\n';
    for(auto i:ans) fout<<i.first<<' '<<i.second<<'\n';
}