#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int first,second,third;
} v[400001];
int parent[200001],Rank[200001];
int find(int i)
{
    while(parent[i]!=i)
    {
i=parent[i];    }
    return i;
}
void Union(int x, int y)
{
    if(Rank[x]<Rank[y])
    {
        parent[x]=y;
    }
    if(Rank[y]<Rank[x])
    {
        parent[y]=x;
    }
    if(Rank[x]==Rank[y])
    {
        parent[x]=y;
        Rank[y]++;
    }
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,e,l;
    fin>>n>>e;
    for(int i=1; i<=e; i++)
    {
        fin>>v[i].first>>v[i].second>>v[i].third;
    }
    sort(v+1,v+e+1,[](edge a,edge b)
    {
        return a.third<b.third;
    });
    for(int i=1; i<=e; i++)
    {
        parent[i]=i;
        Rank[i]=1;
    }
    vector<pair<int,int>>w;
    for(int i=1; i<=e; i++)
    {
        int wix=find(v[i].first),wy=find(v[i].second);
        if(wix!=wy)
        {
            Union(wix,wy);
            w.push_back({v[i].second,v[i].first});
            l+=v[i].third;
        }
    }
    fout<<l<<endl<<n-1<<endl;
    for(int i=0; i<w.size(); i++)
    {
        fout<<w[i].first<<' '<<w[i].second<<endl;
    }
    return 0;
}