#include <fstream>
#include <vector>
#include <climits>
#define nmax 200001
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,apm,x,y,c,t[nmax],cost[nmax];
bool viz[nmax];
struct muchie{
    int x,c;
};
vector<muchie>v[nmax];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    for(int i=2;i<=n;i++)
        cost[i]=INT_MAX;
    for(int i=1;i<=n;i++){
        int mini=INT_MAX,n1=0;
        for(int j=1;j<=n;j++)
            if(!viz[j]&&mini>cost[j])
                mini=cost[j],n1=j;
        viz[n1]=1;
        apm+=cost[n1];
        for(auto j:v[n1])
            if(!viz[j.x]&&j.c<cost[j.x]){
                cost[j.x]=j.c;
                t[j.x]=n1;
            }
    }
    cout<<apm<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        cout<<i<<" "<<t[i]<<'\n';
    return 0;
}