#include <bits/stdc++.h>
#define NMAX 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int cmin[NMAX];
vector < pair <int, int > >sol;
int prec[NMAX];
bool sel[NMAX]; //cele selectate marcate cu 1
vector <pair<int,int > >v[NMAX];
int N,M;
int main()
{
    int x,y,c;
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    int S=0,poz;
    sel[1]=1;
    int start = 1;
    for(int i=1;i<=N;++i)
        cmin[i]=INT_MAX/2;
    for(auto vecin:v[1])
        cmin[vecin.first]=vecin.second, prec[vecin.first] = start;
    prec[start]=0;
    cmin[start]=0;
    for(int i=1;i<=N-1;++i)
    {
        int min1= INT_MAX;
        for(int j=1;j<=N;++j)
        if(cmin[j]<min1 && !sel[j]) {min1=cmin[j], poz=j;}
        sel[poz]=1;
        S+=min1;
        for(auto vecin:v[poz])
        if(cmin[vecin.first] > vecin.second) {
            cmin[vecin.first]=vecin.second;
            prec[vecin.first]=poz;
        }
    }
    fout<<S<<"\n";
    fout<<N-1<<"\n";
    for(int i=2;i<=N;++i)
        {
             if(prec[i])
                sol.push_back({prec[i],i});
        }
    for(auto mc:sol)
        fout<<mc.first << " "<<mc.second<<"\n";
    return 0;
}