#include<fstream>
#include<vector>
#include<set>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector< pair<int, int> > vec[200001];
set<pair <int,int> > heap;
int apm[200001],mc[200001];
int main()
{
    int n, m, x, y, v, i, s = 0, ok=1,cnt=1;
    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> x >> y >> v;
        vec[x].push_back(make_pair(y, v));
        vec[y].push_back(make_pair(x, v));
    }
    /*for (i = 1; i <= n; i++)
        mc[i] = 1001;*/
    /*vector< pair<int, int> >::iterator it;
    for (it = vec[1].begin(); it != vec[i].end(); it++)
        mc[it->first] = it->second; */
    vector< pair<int, int> >::iterator it;
    for (it = vec[1].begin(); it != vec[1].end(); it++)
    {
        heap.insert(make_pair(it->second, it->first));
    }
    apm[1] = 1;
    while (cnt < n)
    {
//        set<pair <int , int> >::iterator it3;
//        for(it3=heap.begin(); it3!=heap.end(); it3++)
//            g<<it3->first<<" "<<it3->second<<" ";
//        g<<"\n";
        cnt++;
        set< pair<int, int> >::iterator it2;
        it2 = heap.begin();
        while (apm[it2->second])
        {
            heap.erase(heap.begin());
            it2 = heap.begin();
        }
        apm[it2->second] = 1;
        mc[it2->second] = it2->first;
        s += it2->first;
        //heap.erase(heap.begin());
        vector< pair<int, int> >::iterator it;
        for (it = vec[it2->second].begin(); it != vec[it2->second].end(); it++)
        {
            if(apm[it->first]==0)
                heap.insert(make_pair(it->second, it->first));
        }

    }
    g << s << '\n' << n - 1<<'\n';
    for (i = 1; i <= n; i++)
    {
        ok = 1;
        vector< pair<int, int> >::iterator it;
        for (it = vec[i].begin(); it != vec[i].end() && ok; it++)
        {
            if (mc[i] == it->second)
            {
                g << i << " " << it->first << '\n';
                ok = 0;
            }
        }
    }
}