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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");


int main()
{
    int n,m,a,b,c;
    f>>n>>m;
    vector< vector< pair<int,int> > >G(n+1);
    set< pair<int, pair<int,int> > >s;
    vector<bool>viz(n+1,0);
    vector< pair<int,int> >edges;
    for(int i=0;i<m;i++)
    {
        f>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
        G[b].push_back(make_pair(a,c));
    }
    viz[1]=1;
    for(auto i:G[1])
        s.insert(make_pair(i.second,make_pair(1,i.first)));///cost,(nod1,nod2)
    int cost=0,nr=0;
    while(nr!=n-1)
    {
        pair<int, pair<int,int> > ind=(*s.begin());
        s.erase(s.begin());
        if(viz[ind.second.second]==0)
        {
            viz[ind.second.second]=1;
            edges.push_back(ind.second);
            nr++;
            cost+=ind.first;
            for(auto i:G[ind.second.second])
                if(viz[i.first]==0)
                    s.insert({i.second,{ind.second.second,i.first}});
        }
    }
    g<<cost<<"\n"<<nr<<"\n";
    for(auto i:edges)
        g<<i.first<<" "<<i.second<<"\n";

    return 0;
}