#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], dc[200001], drum[200001];
int main()
{
    int n, m, x, y, v, i, s = 0, ok=1,cnt=1, ind,mn;
    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));
    }
    vector< pair<int, int> >::iterator it;
    for (it = vec[1].begin(); it != vec[1].end(); it++)
    {
        heap.insert(make_pair(it->second, it->first));
        dc[it->first]=1;
    }
    apm[1] = 1;
    drum[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;
        s += it2->first;
        vector< pair<int, int> >::iterator it;
        for (it = vec[it2->second].begin(); it != vec[it2->second].end(); it++)
            //bagam in  heap toate muchiile noului nod care duc intr-un nod nevizitat
        {
            if(apm[it->first]==0)
            {
                heap.insert(make_pair(it->second, it->first)); //cost nod
                dc[it->first]=it2->second;
            }
        }
//        g<<it2->second<<" ";
        drum[it2->second]=dc[it2->second];
//        g<<dc[it2->second]<" ";
//               g<<"\n";
    }
    g<<s<<"\n"<<n-1<<"\n";
    for(i=2; i<=n; i++)
        g<<i<<" "<<drum[i]<<"\n";
}