#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii
{
    int x, y, c;
} v[10000];
class cmp
{
public:
    bool operator () (const muchii &a, const muchii &b)
    const
    {
        return a.c>b.c;
    }
};
vector <pair <int, int> > G[200001];
priority_queue < muchii, vector < muchii >, cmp > pq;

int n,m,x,y,c,s;
int t[1000];
bool viz[1000];
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }
    muchii x;
    viz[1]=1;
    for(auto i: G[1])
    {
        x.x=1;
        x.y=i.first;
        x.c=i.second;
        pq.emplace(x);
    }
    for(int i=1; i<=n-1; i++)
    {
        muchii nod;
        do
        {
            nod=pq.top();
            pq.pop();
        }
        while(viz[nod.x]+viz[nod.y]!=1);
        s+=nod.c;
            if(viz[nod.x])
            {
                t[nod.y]=nod.x;
                for(auto i: G[nod.y])
                {
                    x.x=nod.y;
                    x.y=i.first;
                    x.c=i.second;
                    pq.emplace(x);
                }
                viz[nod.y]=1;
            }
            else
            if(viz[nod.x])
            {
                t[nod.x]=nod.y;
                for(auto i: G[nod.x])
                {
                    x.x=nod.x;
                    x.y=i.first;
                    x.c=i.second;
                    pq.emplace(x);
                }
                viz[nod.x]=1;
            }
    }
    g<<s<<'\n';
    g<<n-1<<'\n';
    for(int i=1; i<=n; i++)
        if(t[i])
        g<<i<<' '<<t[i]<<'\n';
    return 0;
}