#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define NMAX 108

const int INF = 1e9+1;

ifstream fin ("prim.in");
ofstream fout ("prim.out");

struct muchie
{
    int a, cost;
};

struct edge
{
    int a, b, cost;
    friend bool operator < (edge m1, edge m2);
};

int n,i,j,m,a,b,cost,answer;

vector<muchie>g[NMAX];

priority_queue<edge>h;

vector<edge>sol;

bool uz[NMAX];

int cmin[NMAX];// cmin[x]=costul minim al unei muchii ce

int pre[NMAX];

void input ();

void prim();

bool operator < (edge m1, edge m2)
{
    return m1.cost>m2.cost;
}

int main()
{
    input();
    prim();
    for (i=1; i<=n; i++)
    {
        answer+=cmin[i];
    }
    fout<<answer<<'\n';
    fout<<n-1<<'\n';
    for (auto it : sol)
    {
        fout<<it.a<<' '<<it.b<<'\n';
    }
    return 0;
}

void prim()
{
    edge ads,sduf;
    int start,costminim,vfmin;
    start=1;
    uz[start]=1;
    for (auto it : g[start])
    {
        ads.b=start,ads.a=it.a;
        ads.cost=it.cost;
        h.push(ads);
    }
    for (i=1; i<n; )
    {
        ads=h.top();
        h.pop();
        if (uz[ads.a]==0)
        {
            uz[ads.a]=1;
            ++i;
            answer+=ads.cost;
            sol.push_back(ads);
            for (auto it : g[ads.a])
            {
                if (!uz[it.a])
                {
                    sduf.a=it.a;
                    sduf.b=ads.a;
                    sduf.cost=it.cost;
                    h.push(sduf);
                }
            }
        }
    }
}

void input( )
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>a>>b>>cost;
        g[a].push_back({b,cost});
        g[b].push_back({a,cost});
    }
}