#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];
struct pizza
{
    int x, c;
}drum[200001];
int main()
{
    int n, m, x, y, v, i, s = 0,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));
    }
    vector< pair<int, int> >::iterator it;
    for (it = vec[1].begin(); it != vec[1].end(); it++)
    {
        heap.insert(make_pair(it->second, it->first));
        drum[it->first].x=1;
        drum[it->first].c=it->second;
    }
    apm[1]=1;
    drum[1].c=0;
    drum[1].x=0;
    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;
        //drum[it2->second]=dc[it2->second];
        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
                if(drum[it->first].c!=0)
                {
                    if(drum[it->first].c>it->second)
                    {
                        drum[it->first].c=it->second;
                        drum[it->first].x=it2->second;
                    }
                }
                else
                {
                    drum[it->first].c=it->second;
                    drum[it->first].x=it2->second;
                }
            }
        }
    }
    g<<s<<"\n"<<n-1<<"\n";
    for(i=2; i<=n; i++)
        g<<i<<" "<<drum[i].x<<"\n";
}