#include <fstream>
#include <vector>
#include <cstring>
#define dim 400005
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int i,j,nod,n,m,a,b,c,x,f[dim],poz[dim],H[dim],hdim,vec[dim],sol;
vector <pair<int,int> > v[dim],apm;
void apm_insert(int x)
{
    for(int i=0;i<v[x].size();i++)
    {
        int nod = v[x][i].first;
        int cost = v[x][i].second;
        f[nod]=min(f[nod],cost);
        if(f[nod]==cost)
            vec[nod]=x;
    }
}
void up(int k)
{
    while(k/2)
    {
        if(f[H[k/2]] > f[H[k]])
        {
            swap(poz[H[k/2]],poz[H[k]]);
            swap(H[k/2],H[k]);
            k/=2;
        }
        else
            break;
    }
}
void down(int k)
{
    while(2*k<=hdim)
    {
        int po=2*k;
        if(po+1<=hdim && f[H[po]] > f[H[po+1]])
            po++;
        if(f[H[k]] > f[H[po]])
        {
            swap(poz[H[k]],poz[H[po]]);
            swap(H[k],H[po]);
            k=po;
        }
        else
            break;
    }
}
void heap_insert(int nod)
{
    H[++hdim]=nod;
    poz[nod]=hdim;
    up(hdim);
}
int heap_extract()
{
    int x=H[1];
    swap(H[1],H[hdim]);
    swap(poz[H[1]],poz[H[hdim]]);
    hdim--;
    down(1);
    poz[x]=0;
    return x;
}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    memset(f,inf,sizeof(f));
    f[1]=0;
    apm_insert(1);
    for(i=2;i<=n;i++){
        heap_insert(i);
    }
    for(i=1;i<n;i++){
        x=heap_extract();
        apm_insert(x);
        sol+=f[x];
        apm.push_back(make_pair(x,vec[x]));
        for(j=0;j<v[x].size();j++){
            nod=v[x][j].first;
            if(poz[nod]){
                up(poz[nod]);
            }

        }
    }
    fout<<sol<<"\n";
    fout<<n-1<<"\n";
    for(i=0;i<n-1;i++){
        fout<<apm[i].first<<" "<<apm[i].second<<"\n";
    }

    return 0;
}