#include <bits/stdc++.h>
#define N 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
long long s=0;
int d[N],t[N];
bool viz[N];
struct Muchie
{
    int v,c;
};
set<Muchie>a[N];
struct MuchieSol
{
    int x,y;
};
set<MuchieSol>sol;
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        {
        int u,v,c;
        fin>>u>>v>>c;
        a[u].insert({v,c});
        a[v].insert({u,c});
    }
    for(int i=1; i<=n; i++) d[i]=1e9;
    d[1]=0;
    for(int p=1; p<=n; p++)
    {
        int u=-1;
        int dmin=1e9;
        for(int j=1; j<=n; j++)
            if(!viz[j] && d[j]<dmin) dmin=d[j],u=j;
        if(u==-1 || dmin==1e9) break;
        viz[u]=1;
        if(u!=1)
        {
            s+=dmin;
            sol.insert({t[u],u});
        }
        for(auto& vecin:a[u]){
            int v=vecin.v;
            int c=vecin.c;
            if(!viz[v] && c<d[v]) d[v]=c,t[v]=u;
        }
    }
    fout<<s<<"\n";
    fout<<sol.size()<<"\n";
    for(auto& r:sol)
        fout<<r.x<<" "<<r.y<<"\n";
    return 0;
}